网站正在建设中单页线下推广公司

哈希表

key是唯一的，value可以重复

哈希表和我们常说的 Map（键值映射）不是同一个东西。

【Map】是一个 Java 接口，仅声明了若干个方法，并没有给出方法的具体实现；HashMap 这种数据结构根据自身特点实现了这些操作。

可以说hashmap的get、put、remove等方法复杂度为O(1)，但是map接口的复杂度不一定，需要看他底层数据结构的实现方法。

【哈希函数】的作用是把任意长度的输入（key）转化成固定长度的输出（索引），类比数组。增删查改时都会用到哈希函数，所以哈希函数的算法设计与复杂度紧紧相关。

任意 Java 对象都有一个 int hashCode() 方法，在实现自定义的类时，如果不重写这个方法，返回值可以认为是该对象的内存地址。一个对象的内存地址显然是全局唯一的一个整数。

所以调用 key 的 hashCode() 方法就相当于把 key 转化成了一个整数，且这个整数是全局唯一的。

【哈希冲突】两个不同的key通过哈希函数得到了相同的索引。因为 hash 函数相当于把一个无穷大的空间映射到了一个有限的索引空间，所以必然会有不同的 key 映射到同一个索引上。

【拉链法和开放寻址法】用于解决哈希冲突。

【负载因子】= size/table.length，需要避免负载因子过大，会导致哈希表性能下降。理论上拉链法负载因子能达到无穷大，开放寻址法负载因子不超过1。

【扩容】当哈希表内元素达到负载因子时，哈希表会扩容。

---

1. 数组实现hash表

数组keys存储所有键，indexMap存储键在数组中的索引，valueMap存储键值对，增删查改时实现时间复杂度为O(1)

编写randomKey()，在hash表中实现等概率随机生成一个键，解决了hash表中，因为哈希冲突产生的“空洞”导致不能等概率读取的问题。

class RandomizedHashTable {constructor() {this.keys = []; //存储所有键this.indexMap = new Map();  //键：索引，存储键在数组中的索引this.valueMap = new Map();  //键：值，存储键值对}//添加元素mySet(key, value) {//如果键不存在，则新建if (!this.valueMap.has(key)) {this.indexMap.set(key, this.keys.length);this.keys.push(key);}//如果键已经存在，直接修改值valuethis.valueMap.set(key, value);}//获取元素myGet(key) {return this.valueMap.get(key);}//删除元素myDelete(key) {//如果key不存在if (! this.valueMap.has(key)) { return false;}//如果key存在//通过键:索引map获取要删除元素的索引const index = this.indexMap.get(key);//获取最后一个元素的键const lastKey = this.keys[this.keys.length - 1];//将最后一个元素移动到当前删除位置this.keys[index] = lastKey;this.indexMap.set(lastKey, index);//删除最后一个元素this.keys.pop();this.indexMap.delete(key);this.valueMap.delete(key);return true;}//均匀随机生成一个键randomKey() {if (this.keys.length === 0) { return false;}const randomIndex = Math.floor(Math.random() * this.keys.length);return this.keys[randomIndex];}
}const example =new RandomizedHashTable();
example.mySet(1, 'a');
example.mySet(2, 'b');
example.mySet(3, 'c');
console.log(example.randomKey());

2. 双链表实现hash表

【算法实现：】

注意：hash表与hash链表同步操作

class ListNode {constructor(key, value) {this.key = key;this.value = value;this.prev = null;this.next = null;}
}class HashLinkedList {constructor(maxsize = 10) {this.maxsize = maxsize;this.hashMap = new Map();this.head = new ListNode(0, 0);this.tail = new ListNode(0, 0);this.head.next = this.tail;this.tail.prev = this.head;}//移动到头部moveToHead(node) {//先断开原本连接node.prev.next = node.next;node.next.prev = node.prev;//插入到头部node.prev = this.head;node.next = this.head.next;this.head.next.prev = node;this.head.next = node;}// 增加到头部操作addToHead(node) {node.prev = this.head;node.next = this.head.next;this.head.next.prev = node;this.head.next = node;}//删除尾部元素removeTail() {const lastNode = this.tail.prev;//从hash表中删除this.hashMap.delete(lastNode.key);//从hash链表中删除lastNode.prev.next = this.tail;this.tail.prev = lastNode.prev;return lastNode;}//查询操作myGet(key) {if(!this.hashMap.has(key)) { return -1;}const node = this.hashMap.get(key);this.moveToHead(node);return node.value;}//插入/更新myPut(key, value) {//如果key已经存在则更新valueif(this.hashMap.has(key)) {const node = this.hashMap.get(key);node.value = value;//移动到头节点处this.moveToHead(node);return;}//如果key不存在则添加新key和valueconst newnode = new ListNode(key, value);//注意是添加一个节点对象newnodethis.hashMap.set(key,newnode);this.addToHead(newnode);//如果超过容量则删除尾部元素if(this.hashMap.size > this.maxsize) {this.removeTail();}}//删除操作myDelete(key) {if(!this.hashMap.has(key)) { return false;}const node = this.hashMap.get(key); //从链表删除node.prev.next = node.next;node.next.prev = node.prev;//从hash表删除this.hashMap.delete(key);return true;}
}const example = new HashLinkedList(2);
example.myPut(1, 'a');
example.myPut(2, 'b');
console.log(example.myGet(1));