哈希表hash算法的冲突问题

Question

已知字符串的hash算法如下：

function hashCode(str) {
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    hash = hash * 31 + str.charCodeAt(i);
  }
  return hash;
}

找出2^n个hashCode方法返回值相同，且长度为2^n的字符串，提示:hashCode('Aa') == hashCode('BB')。如下图所示：

根据例子可以推论如下：

CC == Bb
DD == Cc
BBBB == BBAa

但是如何找出全部的2^n个字符串还是一点思路都没有

Answer 1

放在主回答里哈。。。

给个思路哈，我们可以认为最终的hash是31进制数，那么我们可以通过以下步骤来从一个字符串构造另一个hashCode相同的字符串：
1.某个位置上的code-31
2.它的前一个位置上的code+1

为了得到合法的字符串，我们要保证code-31和code+1得到某个字母的编码。例如：'y'的编码值为121，121-31=90刚好为'Z'的编码值。

接下来来构造吧，首先有一个字符串xxxxxxxxyy（这里x代表任意字母）我们把最后一个y-31，得到'Z'，倒数第二个y+1，得到'z'，所以hashCode("xxxxxxxxyy")==hashCode("xxxxxxxxzZ")。前面n-2个x可以随机有52^(n-2)个。为什么是52，26个大写字母，26个小写字母。
然后最后两个yy改成xx继续上面的过程。
这样的字符串你可以得到非常多个。

================ 以下是原回答 ===================
题目感觉有点矛盾，如果按照hashCode算法的实现，hashCode('Aa')肯定不等于hashCode('BB')。

下面几组也不可能相等。

Answer 2

这个方法就不该叫hashCode

Answer 3

大佬的回答然我茅塞顿开，根据您的提示写了下：

function hashCode(str) {
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    hash = hash * 31 + str.charCodeAt(i);
  }
  return hash;
}

// 寻找hash冲突

const hash1 = hashCode('Aa'); // 65 * 31 + 97
const hash2 = hashCode('BB'); // 66 * 31 + 66

// 某一位上的code-1，后一位的code+31，其他位置不变

// 可以推测出
// CC = Bb
// BBBB = BBAa

console.log(hash1, hash2);

function isAscii(charCode) {
  return charCode >= 65 && charCode <= 90 || charCode >= 97 && charCode <= 122;
}

function* buildStr(len) {

  const list = [];
  for (let i = 65; i <= 90; i++) {
    list.push(String.fromCharCode(i));
  }
  for (let i = 97; i <= 122; i++) {
    list.push(String.fromCodePoint(i));
  }

  const chars = new Array(len);

  function* _buildStr(chars, pos) {
    if (pos >= len) {
      return yield chars.join('');
    }
    for (let i = 0; i < list.length; i++) {
      chars[pos] = list[i];
      yield* _buildStr(chars, pos + 1);
    }
  }

  return yield* _buildStr(chars, 0);
}

function buildHashCode(n) {

  const len = 2 ** n;

  let results = [];

  const map = {};

  let maxHash = 0;

  for (const str of buildStr(len)) {
    const hash = hashCode(str);
    map[hash] = map[hash] || new Set();
    const charList = str.split('');
    const ret = [];
    _buildHashCode(charList, 0, ret);
    for (const item of ret) {
      map[hash].add(item);
    }
    if (map[hash].size >= len) {
      maxHash = hash;
      break;
    }
  }

  // 没有找到指定长度的，返回所有字符串中hash冲突最多的那些字符串
  if (maxHash === 0) {
    for (const hash of Object.keys(map)) {
      maxHash = Math.max(maxHash,map[hash].length);
    }
  }

  return [...map[maxHash]];

  function _buildHashCode(charList, pos, ret) {
    if (pos + 1 >= charList.length) {
      return;
    }
    let cur = charList[pos];
    let next = charList[pos + 1];

    let charCodeCur = cur.charCodeAt(0) - 1;
    let charCodeNext = next.charCodeAt(0) + 31;

    if (isAscii(charCodeCur) && isAscii(charCodeNext)) {
      charList[pos] = String.fromCodePoint(charCodeCur);
      charList[pos + 1] = String.fromCodePoint(charCodeNext);
      ret.push(charList.join(''));
    }
    _buildHashCode(charList, pos + 1, ret);
    charList[pos] = cur;
    charList[pos + 1] = next;
  }
}

const ret = buildHashCode(2);
for (const str of ret) {
  console.log(str, hashCode(str));
}

输出结果：

2112 2112
Aaaa 2032736
AabB 2032736
AbBa 2032736
AbCB 2032736

对于种子字符串的生成，我目前采用的是生成字符串的全排列，然后从中选取，不知道你还有别的建议不？