用于数组位置/字符串的XOR散列算法的名称

Question

我有下面的C代码：

http://marknelson.us/1989/10/01/lzw-data-compression/

它指出，它使用异或散列算法来避免搜索子字符串数组元素，而是为子字符串生成一个“地址”。

还有一个散列函数，在我看来，下面的行是主要的部分：

index = (hash_character << HASHING_SHIFT) ^ hash_prefix;

• 这里我们有一个整数值，从4位移到左边(根据常量的定义)。
• 然后，该值将得到一个与另一个整数值一起应用的XOR。

我非常肯定，移位部分只是为了摆脱未使用的比特，然后一个简单的XOR操作被应用于一个非常短的子字符串，从12位到16位；不过我可能错了。

解释这一特定异或散列算法的名称或可能的算法名是什么？

#define BITS 12                   /* Setting the number of bits to 12, 13*/
#define HASHING_SHIFT (BITS-8)    /* or 14 affects several constants.    */
#define MAX_VALUE (1 << BITS) - 1 /* Note that MS-DOS machines need to   */
#define MAX_CODE MAX_VALUE - 1    /* compile their code in large model if*/
                                  /* 14 bits are selected.               */
#if BITS == 14
  #define TABLE_SIZE 18041        /* The string table size needs to be a */
#endif                            /* prime number that is somewhat larger*/
#if BITS == 13                    /* than 2**BITS.                       */
  #define TABLE_SIZE 9029
#endif
#if BITS <= 12
  #define TABLE_SIZE 5021
#endif

.

.

.

/*
** This is the hashing routine.  It tries to find a match for the prefix+char
** string in the string table.  If it finds it, the index is returned.  If
** the string is not found, the first available index in the string table is
** returned instead.
*/

int find_match(int hash_prefix,unsigned int hash_character)
{
int index;
int offset;

  index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
  if (index == 0)
    offset = 1;
  else
    offset = TABLE_SIZE - index;
  while (1)
  {
    if (code_value[index] == -1)
      return(index);
    if (prefix_code[index] == hash_prefix &&
        append_character[index] == hash_character)
      return(index);
    index -= offset;
    if (index < 0)
      index += TABLE_SIZE;
  }
}

Answer 1

在Bruno Preiss的数据结构和算法中，使用Java中的面向对象设计模式描述了类似的哈希函数“John & Sons，2000”

哈希函数的一个不错的(但有点过时的)调查是这里。该函数在调查中被命名为"BPhash“。在我看来，LZW哈希函数非常简单。到目前为止，可能有更好的哈希函数，产生较少的干扰冲突，从而提高了散列的效率/有效性。