JavaScript数据结构与算法（七）散列表

散列算法的作用是尽可能快的在数据结构中找到一个值，使用散列函数就可以知道值的具体位置，快速检索到该值，而不需要像其他的数据结构一样需要迭代整个数据结构才能找到该值。散列函数的作用是给定一个键值，然后返回值在表中的地址。话不多说，直接上实现散列表的代码。

散列表

创建散列表

和之前一样，我们继续搭建类的骨架

function defaultToString(item) {
  if (item === null) {
    return 'NULL';
  } if (item === undefined) {
    return 'UNDEFINED';
  } if (typeof item === 'string' || item instanceof String) {
    return `${item}`;
  }
  return item.toString();
};

class ValuePair{
    constructor(key,value){
        this.key = key;
        this.value = value;
    };
    toString(){
        return `[$(this.key):$(this.value)]`;
    };
};

class HashTable {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn;
    this.table = {};
  };

创建散列函数

loseloseHashCode(key) {
    if (typeof key === 'number') {
      return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) {
      hash += tableKey.charCodeAt(i);
    }
    return hash % 37;
  };

hashCode(key) {
    return this.loseloseHashCode(key);
  };

将键和值添加到散列表中

put(key, value) {
    if (key != null && value != null) {
      const position = this.hashCode(key);
      this.table[position] = new ValuePair(key, value);
      return true;
    }
    return false;
  }

从散列表中移除一个值

remove(key) {
    const hash = this.hashCode(key);
    const valuePair = this.table[hash];
    if (valuePair != null) {
      delete this.table[hash];
      return true;
    }
    return false;
  }

转为字符串

toString() {
    if (this.isEmpty()) {
      return '';
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString},{${keys[i]} => ${this.table[keys[i]].toString()}}`;
    }
    return objString;
  }

处理散列函数中的冲突

有时候，一些不同的键会拥有相同的散列值，后添加的元素会覆盖之前添加的值。那么问题来了，我们借用散列表的目的就是把所有的数据保存起来，而不是丢失。接下来提供解决这种冲突的方法。

分离链接

为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突最简单的方法，但是在HashTable实例外还需要额外的存储空间。

创建散列类骨架

class HashTableSeparateChaining {
  constructor(toStrFn = defaultToString) {
    this.toStrFn = toStrFn;
    this.table = {};
  }

添加新元素

put(key, value) {
    if (key != null && value != null) {
      const position = this.hashCode(key);
      if (this.table[position] == null) {
        this.table[position] = new LinkedList();
      }
      this.table[position].push(new ValuePair(key, value));
      return true;
    }
    return false;
  }

查询元素的值

get(key) {
    const position = this.hashCode(key);
    const linkedList = this.table[position];
    if (linkedList != null && !linkedList.isEmpty()) {
      let current = linkedList.getHead();
      while (current != null) {
        if (current.element.key === key) {
          return current.element.value;
        }
        current = current.next;
      }
    }
    return undefined;
  }

删除方法

remove(key) {
    const position = this.hashCode(key);
    const linkedList = this.table[position];
    if (linkedList != null && !linkedList.isEmpty()) {
      let current = linkedList.getHead();
      while (current != null) {
        if (current.element.key === key) {
          linkedList.remove(current.element);
          if (linkedList.isEmpty()) {
            delete this.table[position];
          }
          return true;
        }
        current = current.next;
      }
    }
    return false;
  }

线性探查

将元素直接存储在表中，当想添加元素时，索引为position的位置已经被占据了，就尝试position+1的位置，以此类推，知道找到一个空闲的位置，将元素添加进去。线性探查分为两种，一种是软删除，一种是移动元素法。

软删除（惰性删除）

软删除是指散列表被操作过后，我们会留一下一个标记来表示被删除了但实际情况并没有真的删除它。操作完后，会留下若干删除位置的散列表，但这会降低散列表的效率，违背了散列表快速搜索的初衷。类骨架跟之前的一样，这里就不做展示了。具体实现代码如下：

put方法实现

put(key, value) {
    if (key != null && value != null) {
      const position = this.hashCode(key);
      if (
        this.table[position] == null
        || (this.table[position] != null && this.table[position].isDeleted)//位置上没有元素或者被删除了，
      ) {
        this.table[position] = new ValuePairLazy(key, value);
      } else {
        let index = position + 1;
        while (this.table[index] != null && !this.table[position].isDeleted) {
          index++;
        }
        this.table[index] = new ValuePairLazy(key, value);
      }
      return true;
    }
    return false;
  }

get方法实现

get(key) {

const position = this.hashCode(key);
if (this.table[position] != null) {
  if (this.table[position].key === key && !this.table[position].isDeleted) {
    return this.table[position].value;
  }
  let index = position + 1;
  while (
    this.table[index] != null
    && (this.table[index].key !== key || this.table[index].isDeleted)
  ) {
    if (this.table[index].key === key && this.table[index].isDeleted) {
      return undefined;
    }
    index++;
  }
  if (
    this.table[index] != null
    && this.table[index].key === key
    && !this.table[index].isDeleted
  ) {
    return this.table[position].value;
  }
}
return undefined;

}

remove方法实现

remove(key) {
    const position = this.hashCode(key);
    if (this.table[position] != null) {
      if (this.table[position].key === key && !this.table[position].isDeleted) {
        this.table[position].isDeleted = true;
        return true;
      }
      let index = position + 1;
      while (
        this.table[index] != null
        && (this.table[index].key !== key || this.table[index].isDeleted)
      ) {
        index++;
      }
      if (
        this.table[index] != null
        && this.table[index].key === key
        && !this.table[index].isDeleted
      ) {
        this.table[index].isDeleted = true;
        return true;
      }
    }
    return false;
  }

移动元素

put方法实现

put(key, value) {
    if (key != null && value != null) {
      const position = this.hashCode(key);
      if (this.table[position] == null) {
        this.table[position] = new ValuePair(key, value);
      } else {
        let index = position + 1;
        while (this.table[index] != null) {
          index++;
        }
        this.table[index] = new ValuePair(key, value);
      }
      return true;
    }
    return false;
  }

get方法实现

get(key) {
    const position = this.hashCode(key);
    if (this.table[position] != null) {
      if (this.table[position].key === key) {
        return this.table[position].value;
      }
      let index = position + 1;
      while (this.table[index] != null && this.table[index].key !== key) {
        index++;
      }
      if (this.table[index] != null && this.table[index].key === key) {
        return this.table[position].value;
      }
    }
    return undefined;
  }

remove方法实现

remove(key) {
    const position = this.hashCode(key);
    if (this.table[position] != null) {
      if (this.table[position].key === key) {
        delete this.table[position];
        this.verifyRemoveSideEffect(key, position);
        return true;
      }
      let index = position + 1;
      while (this.table[index] != null && this.table[index].key !== key) {
        index++;
      }
      if (this.table[index] != null && this.table[index].key === key) {
        delete this.table[index];
        this.verifyRemoveSideEffect(key, index);
        return true;
      }
    }
    return false;
  }

还有一种深受社区喜欢的方法，双散列表,也就是创建更好的散列函数

djb2HashCode(key){
    const tableKey = this.toStrFn(key);
    let hash = 5381;
    for(let i = 0;i < tableKey.length;i++){
    hash = (hash * 33)+ tableKey.charCodeAt(i);
    };
    return hash % 1013;
}