查询网站是否安全,南宁企业网站建设制作,建设摩托车官网的网站首页,深圳自定义网站开发目录
一、介绍
二、哈希数据结构
三、✍️实现哈希散列
1. 哈希碰撞#x1f4a5;
2. 拉链寻址⛓️
3. 开放寻址⏩
4. 合并散列 一、介绍
哈希表#xff0c;也被称为散列表#xff0c;是一种重要的数据结构。它通过将关键字映射到一个表中的位置来直接访问记录#…目录
一、介绍
二、哈希数据结构
三、✍️实现哈希散列
1. 哈希碰撞
2. 拉链寻址⛓️
3. 开放寻址⏩
4. 合并散列 一、介绍
哈希表也被称为散列表是一种重要的数据结构。它通过将关键字映射到一个表中的位置来直接访问记录以此加快查找速度。这种映射函数被称为散列函数。哈希表的历史可以追溯到上个世纪 50 年代由美国计算机科学家拉宾·珀尔Rabin Pearl和罗伯特·韦伯Robert Weiss发明。自那时以来哈希表已经成为了计算机科学和编程中不可或缺的一部分广泛应用于各种领域。 二、哈希数据结构
在计算机中数据的存储结构主要有两种数组和链表。数组的优势是长度固定每个下标都指向唯一的一个值但同时也存在长度固定的缺点。哈希表则是一种介于数组和链表之间能够动态调整大小的数据结构。
使用数组存放元素都是按照顺序存放的当需要获取某个元素的时候则需要对数组进行遍历获取到指定的值时间复杂度是 O(n)。哈希表的主要优点在于它可以提供快速的插入操作和查找操作无论哈希表中含有多少条数据插入和查找的时间复杂度都是为 O(1)这一特性使得哈希表在处理大量数据时具有很高的效率。 三、✍️实现哈希散列
源码地址hash_table
1. 哈希碰撞
说明通过模拟简单 HashMap 实现去掉拉链寻址等设计验证元素索引位置的碰撞。
public class HashMap01K, V implements MapK, V {private Logger logger LoggerFactory.getLogger(HashMap01.class);private Object[] tab new Object[8];Overridepublic void put(K key, V value) {int idx key.hashCode() (tab.length - 1);tab[idx] value;}Overridepublic V get(K key) {int idx key.hashCode() (tab.length - 1);return (V) tab[idx];}
} HashMap01 的实现只是通过哈希计算出的下标散列存放到固定的数组内。那么这样当发生元素下标碰撞时原有的元素就会被新的元素替换掉即哈希碰撞。 测试
Test
public void test_hashMap01() {MapString, String map new HashMap01();map.put(01, 小火龙);map.put(04, 火爆猴);logger.info(碰撞前 key{} value{},01,map.get(01));// 模拟下标碰撞map.put(09,可达鸭);map.put(12,呆呆兽);logger.info(碰撞后 key{} value{},01,map.get(01));
} 10:50:36.662 [main] INFO com.pjp.hash_table.test.HashTableTest - 碰撞前 key01 value小火龙
10:50:36.666 [main] INFO com.pjp.hash_table.test.HashTableTest - 碰撞后 key01 value呆呆兽
通过测试结果可以看到碰撞前 map.get(01) 的值是 小火龙两次下标索引碰撞后存放的值则是 呆呆兽这也就是使用哈希散列必须解决的一个问题无论是在已知元素数量的情况下通过扩容数组长度解决还是把碰撞的元素通过链表存放都是可以的。 2. 拉链寻址⛓️
说明既然我们没法控制元素不碰撞但我们可以对碰撞后的元素进行管理。比如像 HashMap 中拉链法一样把碰撞的元素存放到链表上。这里我们就来简化实现一下。
public class HashMap02ByZipperK, V implements MapK, V {private LinkedListNodeK, V[] tab new LinkedList[8];Overridepublic void put(K key, V value) {int idx key.hashCode() (tab.length - 1);if (tab[idx] null) {tab[idx] new LinkedList();tab[idx].add(new Node(key, value));} else {tab[idx].add(new Node(key, value));}}Overridepublic V get(K key) {int idx key.hashCode() (tab.length - 1);for (NodeK, V kvNode : tab[idx]) {if (key.equals(kvNode.getKey())) {return kvNode.getValue();}}return null;}static class NodeK, V {final K key;V value;public Node(K key, V value) {this.key key;this.value value;}public K getKey() {return key;}public V getValue() {return value;}}
} 因为元素在存放到哈希桶上时可能发生下标索引膨胀所以这里我们把每一个元素都设定成一个 Node 节点这些节点通过 LinkedList 链表关联也可以通过 Node 节点构建出链表 next 元素即可。那么这时候在发生元素碰撞相同位置的元素就都被存放到链表上了获取的时候需要对存放多个元素的链表进行遍历获取。 测试
Test
public void test_hashMap02() {MapString, String map new HashMap02ByZipper();map.put(01, 小火龙);map.put(04, 火爆猴);logger.info(碰撞前 key{} value{},01,map.get(01));// 模拟下标碰撞map.put(09,可达鸭);map.put(12,呆呆兽);logger.info(碰撞后 key{} value{},01,map.get(01));
} 12:19:15.505 [main] INFO com.pjp.hash_table.test.HashTableTest - 碰撞前 key01 value小火龙
12:19:15.509 [main] INFO com.pjp.hash_table.test.HashTableTest - 碰撞后 key01 value小火龙
前后获取 01 位置元素都是 小火龙 元素没有被替换因为相同索引位置的元素放到链表上去了。 3. 开放寻址⏩
说明除了对哈希桶上碰撞的索引元素进行拉链存放还有不引入新的额外的数据结构只是在哈希桶上存放碰撞元素的方式。它叫开放寻址也就是 ThreaLocal 中运用斐波那契散列开放寻址的处理方式。
public class HashMap03ByOpenAddressingK, V implements MapK, V {private final NodeK, V[] tab new Node[8];Overridepublic void put(K key, V value) {int idx key.hashCode() (tab.length - 1);if (tab[idx] null) {tab[idx] new Node(key, value);} else {for (int i idx; i tab.length; i) {if (tab[i] null) {tab[i] new Node(key, value);break;}}}}Overridepublic V get(K key) {int idx key.hashCode() (tab.length - 1);for (int i idx; i tab.length; i) {// 在开放寻址法中如果tab[i]为null则表示该位置没有存储任何元素因此不需要进行后续的比较操作if (tab[i] ! null tab[i].key key) {return tab[i].value;}}return null;}static class NodeK, V {final K key;V value;public Node(K key, V value) {this.key key;this.value value;}}
} 开放寻址的设计会对碰撞的元素寻找哈希桶上新的位置这个位置从当前碰撞位置开始向后寻找直到找到空的位置存放。在 ThreadLocal 的实现中会使用斐波那契散列、索引计算累加、启发式清理、探测式清理等操作以保证尽可能少的碰撞。 测试
Test
public void test_hashMap03() {MapString, String map new HashMap03ByOpenAddressing();map.put(01, 小火龙);map.put(04, 火爆猴);logger.info(碰撞前 key{} value{},01,map.get(01));// 模拟下标碰撞map.put(09,可达鸭);map.put(12,呆呆兽);logger.info(碰撞后 key{} value{},01,map.get(01));
} 15:57:33.310 [main] INFO com.pjp.hash_table.test.HashTableTest - 碰撞前 key01 value小火龙
15:57:33.313 [main] INFO com.pjp.hash_table.test.HashTableTest - 碰撞后 key01 value小火龙
15:57:33.313 [main] INFO com.pjp.hash_table.test.HashTableTest - 数据结构HashMap{tab[null,{key:01,value:小火龙},{key:09,value:可达鸭},{key:12,value:呆呆兽},{key:04,value:火爆猴},null,null,null]}
通过测试结果可以看到开放寻址对碰撞元素的寻址存放也是可用解决哈希索引冲突问题的。 4. 合并散列
说明合并散列是开放寻址和单独链接的混合碰撞的节点在哈希表中链接。此算法适合固定分配内存的哈希桶通过存放元素时识别哈希桶上的最大空槽位来解决合并哈希中的冲突。
public class HashMap04ByCoalescedHashingK, V implements MapK, V {private final NodeK, V[] tab new Node[8];Overridepublic void put(K key, V value) {int idx key.hashCode() (tab.length - 1);if (tab[idx] null) {tab[idx] new Node(key, value);}int cursor tab.length - 1;while (tab[cursor] ! null tab[cursor].key ! key) {--cursor;}tab[cursor] new Node(key, value);// 将被碰撞的节点指这个新节点// while 是为了处理被碰撞节点已经指向了节点将被碰撞节点指向的节点指向新节点while (tab[idx].idxOfNext ! 0) {idx tab[idx].idxOfNext;}tab[idx].idxOfNext cursor;}Overridepublic V get(K key) {int idx key.hashCode() (tab.length - 1);while (tab[idx] ! null tab[idx].key ! key) {idx tab[idx].idxOfNext;}if (tab[idx] null) {return null;}return tab[idx].value;}static class NodeK, V {final K key;V value;int idxOfNext;public Node(K key, V value) {this.key key;this.value value;}public K getKey() {return key;}public V getValue() {return value;}public int getIdxOfNext() {return idxOfNext;}public void setIdxOfNext(int idxOfNext) {this.idxOfNext idxOfNext;}}Overridepublic String toString() {return HashMap{ tab JSON.toJSONString(tab) };}
} 合并散列的最大目的在于将碰撞元素链接起来避免因为需要寻找碰撞元素所发生的循环遍历。也就是A、B元素存放时发生碰撞那么在找到A元素的时候可以很快的索引到B元素所在的位置。
同上面测试
15:57:53.650 [main] INFO com.pjp.hash_table.test.HashTableTest - 碰撞前 key01 value小火龙
15:57:53.654 [main] INFO com.pjp.hash_table.test.HashTableTest - 碰撞后 key01 value小火龙
15:57:53.654 [main] INFO com.pjp.hash_table.test.HashTableTest - 数据结构HashMap{tab[null,{idxOfNext:7,key:01,value:小火龙},null,{idxOfNext:0,key:12,value:呆呆兽},{idxOfNext:6,key:04,value:火爆猴},{idxOfNext:3,key:09,value:可达鸭},{idxOfNext:0,key:04,value:火爆猴},{idxOfNext:5,key:01,value:小火龙}]}
相对于直接使用开放寻址这样的挂在链路指向的方式可以提升索引的性能。因为在实际的数据存储上元素的下一个位置不一定空元素可能已经被其他元素占据这样就增加了索引的次数。所以使用直接指向地址的方式会更好的提高索引性能。
