哈希表和哈希冲突：求解《705. 设计哈希集合》和《706. 设计哈希映射》

什么是哈希表，什么是哈希函数，什么是哈希冲突，如何处理哈希冲突，什么是在载荷因子，求解《705. 设计哈希集合》和《706. 设计哈希映射》

哈希表

根据键访问内存储存结构的散列表

哈希函数

将键名映射到哈希表的位置（散列地址）的散列函数**

哈希冲突

不同键名被哈希函数映射到同一散列地址，这些键名是同义词

哈希冲突的处理方法

• 聚集
  • 链地址法：相同哈希值的元素放入同一链表
  • 再哈希法：使用新哈希函数产生新地址
  • 双哈希函数：使用两个哈希函数产生地址
  • 建立公共溢出区
• 开放地址法
  • 线性探测：冲突时，按线性序列1, 2, 3, 4, 5, 6... 探测下一个地址
  • 平方探测：冲突时，按平方序列1, 4, 9, 16, 25, 36...探测下一个地址
  • 伪随机探测：冲突时，按伪随机数序列探索下一个地址

载荷因子

开放地址法：α = 填入表中的元素个数 / 散列表的长度 α 应在 0.7 - 0.8 之间，超过 0.8 ，CPU 的 cache missing 按指数曲线上升

例题

705. 设计哈希集合

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。 实现 MyHashSet 类： void add(key) 向哈希集合中插入值 key 。 bool contains(key) 返回哈希集合中是否存在这个值 key 。 void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

答案

var MyHashSet = function() {
  this.base = 769
  this.data = Array.from({length: this.base}, _ => [])
};

MyHashSet.prototype.add = function(key) {
  const h = this.hash(key)
  if (this.contains(key) === false) this.data[h].push(key)
};

MyHashSet.prototype.remove = function(key) {
  const h = this.hash(key)
  const ar = this.data[h]
  for (let i = 0; i < ar.length; i++) {
    if (ar[i] === key) return ar.splice(i, 1) // 立即返回，不用倒序循环
  }

};

MyHashSet.prototype.contains = function(key) {
  const h = this.hash(key)
  const ar = this.data[h]
  for (let i = 0; i < ar.length; i++) {
    if (ar[i] === key) return true
  }
  return false
};

MyHashSet.prototype.hash = function(key) {
  return key % this.base
}; 

706. 设计哈希映射

不使用任何内建的哈希表库设计一个哈希映射（HashMap）。 实现 MyHashMap 类： MyHashMap() 用空映射初始化对象 void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。 int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。 void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。

答案

var MyHashMap = function() {
  this.base = 769
  this.data = Array.from({length: this.base}, _ => [])
};

MyHashMap.prototype.put = function(key, value) {
  const h = this.hash(key)
  const ar = this.data[h]
  for (let i = 0; i < ar.length; i++) {
    if (ar[i][0] === key) return ar[i][1] = value 
  }
  ar.push([key, value])
};

MyHashMap.prototype.get = function(key) {
  const h = this.hash(key)
  const ar = this.data[h]
  for (let i = 0; i < ar.length; i++) {
    if (ar[i][0] === key) return ar[i][1]
  }
  return -1
};

MyHashMap.prototype.remove = function(key) {
  const h = this.hash(key)
  const ar = this.data[h]
  for (let i = 0; i < ar.length; i++) {
    if (ar[i][0] === key) return ar.splice(i, 1)
  }
};

MyHashMap.prototype.hash = function(key) {
  return key % this.base
};