自己动手实现java数据结构（五）哈希表
发布时间：2020-12-15 05:48:41 所属栏目：安全 来源：网络整理
导读：1.哈希表介绍 前面我们已经介绍了许多类型的数据结构。在想要查询容器内特定元素时，有序向量使得我们能使用二分查找法进行精确的查询(( O(logN)对数复杂度，很高效 )。 可人类总是不知满足，依然在寻求一种更高效的特定元素查询的数据结构， 哈希表/散列表(
1.哈希表介绍 前面我们已经介绍了许多类型的数据结构。在想要查询容器内特定元素时，有序向量使得我们能使用二分查找法进行精确的查询((O(logN)对数复杂度，很高效)。 1.1 哈希算法哈希算法的定义：把任意长度的输入通过哈希算法转换映射为固定长度的输出，所得到的输出被称为哈希值(hashCode =?hash(input))。哈希映射是一种多对一的关系，即多个不同的输入有可能对应着一个相同的哈希值输出；也意味着，哈希映射是不可逆，无法还原的。 举个例子：我们有一个好朋友叫熊大,大家都叫他老熊。可以理解为是一个hash算法：对于一个人名，我们一般称呼为"老" + 姓氏(单姓) (hash(熊大) = 老熊)。同时，我们还有一个好朋友叫熊二,我们也叫他老熊(hash(熊二) = 老熊)。当熊大和熊二两个好朋友同时和我们聚会时，都称呼他们为老熊就不太合适啦，因为这时出现了hash冲突。老熊这个称呼同时对应了多个人，多个不同的输入对应了相同的哈希值输出。 java在Object这一最高层对象中实现了hashCode方法，并允许子类重写更适应自身，冲突概率更低的hashCode方法。 1.2 哈希表实现的基本思路哈希表存储的是key-value键值对结构的数据，其基础是一个数组。 由于采用hash算法会出现hash冲突，一个数组下标对应了多个元素。常见的解决hash冲突的方法有：开放地址法、重新哈希法、拉链法等等，我们的哈希表实现采用的是拉链法解决hash冲突。 采用拉链法的哈希表将内部数组的每一个元素视为一个插槽(slot)或者桶(bucket)，并将数据存放在键值对节点(EntryNode)中。EntryNode除了存放key和value，还维护着一个next节点的引用。为了解决hash冲突，单个插槽内的多个EntryNode构成一个简单的单向链表，插槽指向链表的头部节点，新的数据将会插入当前链表的尾部。 key值不同但映射的hash值相同的元素在哈希表的同一个插槽中以链表的形式共存。
1.3 哈希表的负载因子(loadFactor)：哈希表在查询数据时通过直接计算数据hash值对应的插槽，迅速获取到key值对应的数据，进行非常高效的数据查询。 但依然存在一个问题：虽然设计良好的hash函数可以尽可能的降低hash冲突的概率，但hash冲突还是不可避免的。当发生频繁的哈希冲突时，对应的插槽内可能会存放较多的元素，导致插槽内的链表数据过多。而链表的查询效率是非常低的，在极端情况下，甚至会出现所有元素都映射存放在同一个插槽内，此时的哈希表退化成了一个链表，查询效率急剧降低。 一般的，哈希表存储的数据量一定时，内部数组的大小和数组插槽指向的链表长度成反比。换句话说，总数据量一定，内部数组的容量越大(插槽越多)，平均下来桶链表的长度也就越小，查询效率越高。 同等数据量下，哈希表内部数组容量越大，查询效率越高，但同时空间占用也越高，这本质上是一个空间换时间的取舍。 哈希表允许用户在初始化时指定负载因子(loadFactor)：负载因子代表着存储的总数据量和内部数组大小的比值。插入新数据时，判断哈希表当前的存储量和内部数组的比值是否超过了负载因子。当比值超过了负载因子时，哈希表认为内部过于拥挤，查询效率太低，会触发一次扩容的rehash操作。rehash会对内部数组扩容，将存储的元素重新进行hash映射，使得哈希表始终保持一个合适的查询效率。 通过指定自定义的负载因子，用户可以控制哈希表在空间和时间上取舍的程度，使哈希表能更有效地适应用户的使用场景。 指定的负载因子越大，哈希表越拥挤(负载高，紧凑)，查询效率越低，空间效率越高。 指定的负载因子越小，哈希表越稀疏(负载小，松散)，查询效率越高，空间效率越低。 2.哈希表ADT接口和之前介绍的链表不同，我们在哈希表的ADT接口中暴露出了哈希表内部实现的EntryNode键值对节点。通过暴露出去的public方法，用户在使用哈希表时，可以获得内部的键值对节点，灵活的访问其中的key、value数据(但没有暴露setKey方法，不允许用户自己设置key值)。 public interface Map <K,V>{ /** * 存入键值对 * @param key key值 * value value * @return 被覆盖的的value值 */ V put(K key,V value); * 移除键值对 * 被删除的value的值 V remove(K key); * 获取key对应的value值 * 对应的value值 V get(K key); * 是否包含当前key值 * true：包含 false：不包含 */ boolean containsKey(K key); * 是否包含当前value值 * value value值 * true：包含 false：不包含 containsValue(V value); * 获得当前map存储的键值对数量 * 键值对数量 * int size(); * 当前map是否为空 * true：为空 false：不为空 isEmpty(); * 清空当前map void clear(); * 获得迭代器 * 迭代器对象 Iterator<EntryNode<K,V>> iterator(); * 键值对节点 内部类 * class EntryNode<K,1)">{ final K key; V value; EntryNode<K,1)"> next; EntryNode(K key,V value) { this.key = key; this.value = value; } keyIsEquals(K key){ if(this.key == key){ return true; } if(key == null){ //:::如果走到这步，this.key不等于null，不匹配 false; }else{ return key.equals(this.key); } } EntryNode<K,1)"> getNext() { return next; } void setNext(EntryNode<K,1)"> next) { this.next =public K getKey() { key; } V getValue() { setValue(V value) { value; } @Override String toString() { return key + "=" + value; } } } 3.哈希表实现细节3.1 哈希表基本属性：class HashMap<K,V> implements Map<K,1)">{ * 内部数组 * private EntryNode<K,1)">[] elements; * 当前哈希表的大小 * private size; * 负载因子 * float loadFactor; * 默认的哈希表容量 * final static int DEFAULT_CAPACITY = 16; * 扩容翻倍的基数 * int REHASH_BASE = 2 * 默认的负载因子 * float DEFAULT_LOAD_FACTOR = 0.75f========================================构造方法=================================================== * 默认构造方法 * @SuppressWarnings("unchecked") HashMap() { this.size = 0; this.loadFactor = DEFAULT_LOAD_FACTOR; elements = new EntryNode[DEFAULT_CAPACITY]; } * 指定初始容量的构造方法 * capacity 指定的初始容量 * public HashMap( capacity) { EntryNode[capacity]; } * 指定初始容量和负载因子的构造方法 * capacity 指定的初始容量 * loadFactor 指定的负载因子 * int capacity, loadFactor) { loadFactor; elements = EntryNode[capacity]; } } 3.2 通过hash值获取对应插槽下标：获取hash的方法仅和数据自身有关，不受到哈希表存储数据量的影响。 因此getIndex方法的时间复杂度为O(1)。 * 通过key的hashCode获得对应的内部数组下标 * key 传入的键值key * 对应的内部数组下标 * getIndex(K key){ return getIndex(key,1)">.elements); } * 通过key的hashCode获得对应的内部数组插槽slot下标 * elements 内部数组 * int getIndex(K key,EntryNode<K,1)">[] elements){ ){ ::: null 默认存储在第0个桶内 return 0; }{ int hashCode = key.hashCode(); :::通过 高位和低位的异或运算，获得最终的hash映射，减少碰撞的几率 int finalHashCode = hashCode ^ (hashCode >>> 16); return (elements.length-1) & finalHashCode; } } 3.3 链表查询方法：当出现hash冲突时，会在对应插槽处生成一个单链表。我们需要提供一个方便的单链表查询方法，将增删改查接口的部分公用逻辑抽象出来，简化代码的复杂度。 值得注意的是：在判断Key值是否相等时使用的是EntryNode.keyIsEquals方法，内部最终是通过equals方法进行比较的。也就是说，判断key值是否相等和其它数据结构一样，依然是由equals方法决定的。hashCode方法的作用仅仅是使我们能够更快的定位到所映射的插槽处，加快查询效率。 思考一下，为什么要求在重写equals方法的同时，也应该重写hashCode方法？ * 获得目标节点的前一个节点 * currentNode 当前桶链表节点 * key 对应的key * 返回当前桶链表中"匹配key的目标节点"的"前一个节点" * 注意：当桶链表中不存在匹配节点时，返回桶链表的最后一个节点 * currentNode,K key){ :::不匹配 EntryNode<K,V> nextNode = currentNode.next; :::遍历当前桶后面的所有节点 while(nextNode != :::如果下一个节点的key匹配 if(nextNode.keyIsEquals(key)){ currentNode; }:::不断指向下一个节点 currentNode = nextNode; nextNode = nextNode.next; } } :::到达了桶链表的末尾，返回最后一个节点 currentNode; } 3.4 增删改查接口：哈希表的增删改查接口都是通过hash值直接计算出对应的插槽下标(getIndex方法)，然后遍历插槽内的桶链表进行进一步的精确查询(getTargetPreviousEntryNode方法)。在负载因子位于正常范围内时(一般小于1)，桶链表的平均长度非常短，可以认为单个桶链表的遍历查询时间复杂度为(O(1))。 因此哈希表的增删改查接口的时间复杂度都是O(1)。 @Override V put(K key,V value) { (needReHash()){ reHash(); } :::获得对应的内部数组下标 int index = getIndex(key); :::获得对应桶内的第一个节点 EntryNode<K,V> firstEntryNode = .elements[index]; :::如果当前桶内不存在任何节点 if(firstEntryNode == :::创建一个新的节点 this.elements[index] = new EntryNode<>(key,value); :::创建了新节点，size加1 this.size++; ; } (firstEntryNode.keyIsEquals(key)){ :::当前第一个节点的key与之匹配 V oldValue = firstEntryNode.value; firstEntryNode.value = value; oldValue; }:::不匹配 :::获得匹配的目标节点的前一个节点 EntryNode<K,V> targetPreviousNode = getTargetPreviousEntryNode(firstEntryNode,key); :::获得匹配的目标节点 EntryNode<K,V> targetNode = targetPreviousNode.next; if(targetNode != :::更新value的值 V oldValue = targetNode.value; targetNode.value = value; oldValue; }:::在桶链表的末尾 新增一个节点 targetPreviousNode.next = :::创建了新节点，size加1 ; ; } } } @Override V remove(K key) { ; } :::当前第一个节点的key与之匹配 :::将桶链表的第一个节点指向后一个节点(兼容next为null的情况) this.elements[index] = firstEntryNode.next; :::移除了一个节点 size减一 this.size--:::返回之前的value值 firstEntryNode.value; } targetPreviousNode.next; :::将"前一个节点的next" 指向 "目标节点的next" ---> 相当于将目标节点从桶链表移除 targetPreviousNode.next = targetNode.next; :::移除了一个节点 size减一 targetNode.value; }:::如果目标节点为空，说明key并不存在于哈希表中 V get(K key) { :::当前第一个节点的key与之匹配 ; } } } 3.5 扩容rehash操作：前面提到，当插入数据时发现哈希表过于拥挤，超过了负载因子指定的值时，会触发一次rehash扩容操作。 扩容时，我们的内部数组扩容了2倍，所以对于每一个插槽内的元素在rehash时存在两种可能： 1.依然映射到当前下标插槽处 2.映射到高位下标处(当前下标 + 扩容前内部数组长度大小) 注意观察0，4，8三个元素节点，在扩容前(对4取模)都位于下标0插槽；扩容后，数组容量翻倍(对8取模)，存在两种情况，0，8两个元素哈希值依然映射在下标0插槽(低位插槽)，而元素4则被映射到了下标4插槽(高位插槽)(当前下标(0) + 扩容前内部数组长度大小(4))。 通过遍历每个插槽，将内部元素按顺序进行rehash，得到扩容两倍后的哈希表(数据保留了之前的顺序，即先插入的节点依然位于桶链表靠前的位置)。 和向量扩容一样，虽然rehash操作的时间复杂度为O(n)。但是由于只在插入时偶尔的被触发，总体上看，rehash操作的时间复杂度为O(1)。 哈希表扩容前:
哈希表扩容后: ?
/** * 哈希表扩容 * reHash(){ :::扩容两倍 EntryNode<K,V>[] newElements = new EntryNode[this.elements.length * REHASH_BASE]; :::遍历所有的插槽 for (int i=0; i<this.elements.length; i++) { :::为单个插槽内的元素 rehash reHashSlot(i,newElements); } :::内部数组 ---> 扩容之后的新数组 this.elements = newElements; } * 单个插槽内的数据进行rehash * void reHashSlot(int index,1)">[] newElements){ :::获得当前插槽第一个元素 EntryNode<K,V> currentEntryNode = .elements[index]; if(currentEntryNode == :::当前插槽为空，直接返回 :::低位桶链表 头部节点、尾部节点 EntryNode<K,V> lowListHead = ; EntryNode<K,V> lowListTail = :::高位桶链表 头部节点、尾部节点 EntryNode<K,V> highListHead = ; while(currentEntryNode != :::获得当前节点 在新数组中映射的插槽下标 int entryNodeIndex = getIndex(currentEntryNode.key,newElements); :::是否和当前插槽下标相等 if(entryNodeIndex == index){ :::和当前插槽下标相等 if(lowListHead == ){ :::初始化低位链表 lowListHead = currentEntryNode; lowListTail = currentEntryNode; }{ :::在低位链表尾部拓展新的节点 lowListTail.next = lowListTail.next; } }:::和当前插槽下标不相等 if(highListHead == :::初始化高位链表 highListHead = currentEntryNode; highListTail =:::在高位链表尾部拓展新的节点 highListTail.next = highListTail.next; } } :::指向当前插槽的下一个节点 currentEntryNode = currentEntryNode.next; } :::新扩容elements(index)插槽 存放lowList newElements[index] = lowListHead; :::lowList末尾截断 if(lowListTail != ){ lowListTail.next = :::新扩容elements(index + this.elements.length)插槽 存放highList newElements[index + this.elements.length] = highListHead; :::highList末尾截断 if(highListTail != ){ highListTail.next = ; } } * 判断是否需要 扩容 * needReHash(){ return ((this.size / this.elements.length) > .loadFactor); } 3.6 其它接口实现：containsKey(K key) { V value = get(key); return (value != ); } @Override containsValue(V value) { :::遍历全部桶链表 for (EntryNode<K,V> element : .elements) { :::获得当前桶链表第一个节点 EntryNode<K,V> entryNode = element; :::遍历当前桶链表 while (entryNode != ) { :::如果value匹配 (entryNode.value.equals(value)) { :::返回true ; } { :::不匹配，指向下一个节点 entryNode = entryNode.next; } } } :::所有的节点都遍历了，没有匹配的value ; } @Override size() { .size; } @Override isEmpty() { return (this.size == 0 clear() { :::遍历内部数组，将所有桶链表全部清空 for(this.elements[i] = :::size设置为0 public Iterator<EntryNode<K,1)"> iterator() { Itr(); } @Override String toString() { Iterator<EntryNode<K,V>> iterator = .iterator(); :::空容器 if(!iterator.hasNext()){ return "[]":::容器起始使用"[" StringBuilder s = new StringBuilder("["); :::反复迭代 while(:::获得迭代的当前元素 EntryNode<K,V> data = iterator.next(); :::判断当前元素是否是最后一个元素 iterator.hasNext()){ :::是最后一个元素，用"]"收尾 s.append(data).append("]"); :::返回 拼接完毕的字符串 s.toString(); }:::不是最后一个元素 :::使用","分割，拼接到后面 s.append(data).append(","); } } } 4.哈希表迭代器1. 由于哈希表中数据分布不是连续的，所以在迭代器的初始化过程中必须先跳转到第一个非空数据节点，以避免无效的迭代。 2. 当迭代器的下标到达当前插槽链表的末尾时，迭代器下标需要跳转到靠后插槽的第一个非空数据节点。 * 哈希表 迭代器实现 class Itr implements Iterator<EntryNode<K,1)"> { * 迭代器 当前节点 * */ currentNode; * 迭代器 下一个节点 * nextNode; * 迭代器 当前内部数组的下标 * currentIndex; * 默认构造方法 * private Itr(){ :::如果当前哈希表为空，直接返回 if(HashMap..isEmpty()){ ; } :::在构造方法中，将迭代器下标移动到第一个有效的节点上 :::遍历内部数组，找到第一个不为空的数组插槽slot int i=0; i<HashMap.:::设置当前index this.currentIndex = i; EntryNode<K,V> firstEntryNode = HashMap..elements[i]; :::找到了第一个不为空的插槽slot if(firstEntryNode != :::nextNode = 当前插槽第一个节点 this.nextNode = firstEntryNode; :::构造方法立即结束 ; } } } @Override hasNext() { this.nextNode != ); } @Override public EntryNode<K,1)"> next() { this.currentNode = .nextNode; :::暂存需要返回的节点 EntryNode<K,V> needReturn = .nextNode; :::nextNode指向自己的next this.nextNode = .nextNode.next; :::判断当前nextNode是否为null this.nextNode == :::说明当前所在的桶链表已经遍历完毕 :::寻找下一个非空的插槽 int i=this.currentIndex+1; i<HashMap.:::设置当前index i; EntryNode<K,1)">.elements[i]; :::找到了后续不为空的插槽slot ){ :::nextNode = 当前插槽第一个节点 firstEntryNode; :::跳出循环 break; } } } needReturn; } @Override remove() { this.currentNode == throw new IteratorStateErrorException("迭代器状态异常: 可能在一次迭代中进行了多次remove操作"); } :::获得需要被移除的节点的key K currentKey = .currentNode.key; :::将其从哈希表中移除 HashMap..remove(currentKey); :::currentNode设置为null，防止反复调用remove方法 ; } } 5.哈希表性能5.1 空间效率：哈希表的空间效率很大程度上取决于负载因子。通常，为了保证哈希表查询的高效性，负载因子都设置的比较小(小于1)，因而可能会出现许多空的插槽，浪费空间。 总体而言，哈希表的空间效率低于向量和链表。 5.2 时间效率：一般的，哈希表增删改查接口的时间复杂度都是O(1)。但是出现较多的hash冲突时，冲突范围内的key的增删改查效率较低，时间效率会有一定的波动。 总体而言，哈希表的时间效率高于向量和链表。 哈希表的时间效率很高，可天下没有免费的午餐，据统计，哈希表的空间利用率通常情况下还不到50%。 哈希表是一个使用空间来换取时间的数据结构，对查询性能有较高要求的场合，可以考虑使用哈希表。 6.哈希表总结6.1 当前版本缺陷至此，我们已经实现了一个基础的哈希表，但还存在许多明显缺陷： 1.当hash冲突比较频繁时，查询效率急剧降低。 jdk在1.8版本的哈希表实现(java.util.HashMap)中，对这一场景进行了优化。当内部桶链表的节点个数超过一定数量(默认为8)时，会将插槽中的桶链表转换成一个红黑树(查询效率为O(logN))。 2.不支持多线程 在多线程的环境，并发的访问一个哈希表会导致诸如：扩容时内部节点死循环、丢失插入数据等异常情况。 6.2 查询特定元素的方法我们目前查询特定元素有几种不同的方法： 1.顺序查找 在无序向量或者链表中，查找一个特定元素是通过从头到尾遍历容器内元素的方式实现的，执行速度正比于数据量的大小，顺序查找的时间复杂度为O(n)，效率较低。 2.二分查找 在有序向量以及后面要介绍的二叉搜索树中，由于容器内部的元素是有序的，因此可以通过二分查找比较的方式查询特定的元素，二分查找的时间复杂度为O(logN)，效率较高。 3.哈希查找 在哈希表中，通过直接计算出数据hash值对应的插槽(slot)(时间复杂度O(1))，查找出对应的数据，哈希查找的时间复杂度为O(1)，效率极高。 特定元素的查找方式和排序算法的关系 1.顺序查找对应冒泡排序、选择排序等，效率较低，时间复杂度(O(n2))。 2.二分查找对应快速排序、归并排序等，效率较高，时间复杂度(O(nLogn))。 3.哈希查找对应基排序，效率极高，时间复杂度(O(n))。 在大牛刘未鹏的博客中有更为详细的说明，http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick。 6.3 完整代码哈希表ADT接口:
1 { 2 /** 3 * 存入键值对 4 * key key值 5 value value 6 被覆盖的的value值 7 */ 8 V put(K key,V value); 9 10 11 * 移除键值对 12 13 被删除的value的值 14 15 V remove(K key); 16 17 18 * 获取key对应的value值 19 20 对应的value值 21 22 V get(K key); 23 24 25 * 是否包含当前key值 26 27 true：包含 false：不包含 28 29 containsKey(K key); 30 31 32 * 是否包含当前value值 33 value value值 34 true：包含 false：不包含 35 36 containsValue(V value); 37 38 39 * 获得当前map存储的键值对数量 40 键值对数量 41 * 42 size(); 43 44 45 * 当前map是否为空 46 true：为空 false：不为空 47 48 isEmpty(); 49 50 51 * 清空当前map 52 53 clear(); 54 55 56 * 获得迭代器 57 迭代器对象 58 59 Iterator<EntryNode<K,1)"> iterator(); 60 61 62 * 键值对节点 内部类 63 64 65 K key; 66 V value; 67 EntryNode<K,1)"> next; 68 69 EntryNode(K key,V value) { 70 key; 71 value; 72 } 73 74 keyIsEquals(K key){ 75 key){ 76 ; 77 } 78 79 ){ 80 :::如果走到这步，this.key不等于null，不匹配 81 82 } 83 .key); 84 85 86 87 EntryNode<K,1)"> getNext() { 88 89 90 91 next) { 92 93 94 95 K getKey() { 96 97 98 99 V getValue() { 100 101 102 103 setValue(V value) { 104 105 106 107 @Override 108 String toString() { 109 110 111 } 112 } 哈希表实现:
2 3 ===========================================成员属性================================================ 4 * 内部数组 7 [] elements; 8 9 10 * 当前哈希表的大小 12 size; 13 14 * 负载因子 16 loadFactor; 18 19 * 默认的哈希表容量 21 22 * 扩容翻倍的基数 两倍 27 28 30 * 默认的负载因子 31 32 33 34 ========================================构造方法=================================================== 35 36 * 默认构造方法 37 38 @SuppressWarnings("unchecked") 39 HashMap() { 40 41 DEFAULT_LOAD_FACTOR; 42 elements = EntryNode[DEFAULT_CAPACITY]; 43 44 45 * 指定初始容量的构造方法 47 capacity 指定的初始容量 48 49 @SuppressWarnings("unchecked" capacity) { 51 52 53 elements = EntryNode[capacity]; 54 55 56 * 指定初始容量和负载因子的构造方法 58 59 loadFactor 指定的负载因子 60 61 @SuppressWarnings("unchecked" 62 loadFactor) { 63 64 65 elements = 67 68 ==========================================内部辅助方法============================================= 69 70 * 通过key的hashCode获得对应的内部数组下标 71 key 传入的键值key 对应的内部数组下标 73 74 getIndex(K key){ 75 .elements); 76 77 78 79 * 通过key的hashCode获得对应的内部数组插槽slot下标 80 81 elements 内部数组 82 83 84 [] elements){ 85 86 ::: null 默认存储在第0个桶内 87 88 } 89 key.hashCode(); 91 :::通过 高位和低位的异或运算，获得最终的hash映射，减少碰撞的几率 ); 93 finalHashCode; 94 95 96 97 98 * 获得目标节点的前一个节点 99 currentNode 当前桶链表节点 100 key 对应的key 返回当前桶链表中"匹配key的目标节点"的"前一个节点" 102 * 注意：当桶链表中不存在匹配节点时，返回桶链表的最后一个节点 103 104 105 :::不匹配 106 EntryNode<K,1)"> currentNode.next; 107 :::遍历当前桶后面的所有节点 :::如果下一个节点的key匹配 110 (nextNode.keyIsEquals(key)){ 111 currentNode; 112 }113 :::不断指向下一个节点 114 currentNode = nextNode; 115 nextNode = nextNode.next; 116 117 118 119 :::到达了桶链表的末尾，返回最后一个节点 120 121 122 123 124 * 哈希表扩容 125 126 @SuppressWarnings("unchecked"127 reHash(){ 128 :::扩容两倍 129 EntryNode<K,1)"> REHASH_BASE]; 130 131 :::遍历所有的插槽 132 ) { 133 134 135 136 137 :::内部数组 ---> 扩容之后的新数组 138 newElements; 139 140 141 142 * 单个插槽内的数据进行rehash 143 144 [] newElements){ 145 :::获得当前插槽第一个元素 146 EntryNode<K,1)">.elements[index]; 147 148 :::当前插槽为空，直接返回 149 150 151 152 :::低位桶链表 头部节点、尾部节点 153 EntryNode<K,1)">154 EntryNode<K,1)">155 :::高位桶链表 头部节点、尾部节点 156 EntryNode<K,1)">157 EntryNode<K,1)">158 159 160 :::获得当前节点 在新数组中映射的插槽下标 161 162 :::是否和当前插槽下标相等 163 index){ 164 :::和当前插槽下标相等 165 166 :::初始化低位链表 167 lowListHead = currentEntryNode; 168 lowListTail =169 }170 :::在低位链表尾部拓展新的节点 171 lowListTail.next =172 lowListTail = lowListTail.next; 173 } 174 }175 :::和当前插槽下标不相等 176 177 :::初始化高位链表 178 highListHead =179 highListTail =180 }181 :::在高位链表尾部拓展新的节点 182 highListTail.next =183 highListTail = highListTail.next; 184 185 186 :::指向当前插槽的下一个节点 187 currentEntryNode = currentEntryNode.next; 188 189 190 :::新扩容elements(index)插槽 存放lowList 191 newElements[index] = lowListHead; 192 :::lowList末尾截断 193 194 lowListTail.next = 195 196 197 :::新扩容elements(index + this.elements.length)插槽 存放highList 198 newElements[index + highListHead; 199 :::highList末尾截断 200 201 highListTail.next = 202 203 204 205 206 * 判断是否需要 扩容 207 208 needReHash(){ 209 .loadFactor); 210 211 212 ============================================外部接口================================================ 213 214 @Override 215 216 (needReHash()){ 217 reHash(); 218 219 220 :::获得对应的内部数组下标 221 getIndex(key); 222 :::获得对应桶内的第一个节点 223 EntryNode<K,1)">224 225 :::如果当前桶内不存在任何节点 226 227 :::创建一个新的节点 228 229 :::创建了新节点，size加1 230 231 232 233 234 (firstEntryNode.keyIsEquals(key)){ 235 :::当前第一个节点的key与之匹配 236 V oldValue = firstEntryNode.value; 237 firstEntryNode.value =238 oldValue; 239 }240 :::不匹配 241 242 :::获得匹配的目标节点的前一个节点 243 EntryNode<K,key); 244 :::获得匹配的目标节点 245 EntryNode<K,1)"> targetPreviousNode.next; 246 247 :::更新value的值 248 V oldValue = targetNode.value; 249 targetNode.value =250 251 }252 :::在桶链表的末尾 新增一个节点 253 targetPreviousNode.next = 254 255 256 257 258 259 260 261 262 V remove(K key) { 263 264 265 266 EntryNode<K,1)">267 268 269 270 271 272 273 274 :::当前第一个节点的key与之匹配 275 276 :::将桶链表的第一个节点指向后一个节点(兼容next为null的情况) 277 firstEntryNode.next; 278 :::移除了一个节点 size减一 279 280 :::返回之前的value值 281 282 }283 284 285 286 EntryNode<K,1)">287 288 EntryNode<K,1)">289 290 291 :::将"前一个节点的next" 指向 "目标节点的next" ---> 相当于将目标节点从桶链表移除 292 targetPreviousNode.next = targetNode.next; 293 294 295 296 }297 :::如果目标节点为空，说明key并不存在于哈希表中 298 299 300 301 302 303 304 V get(K key) { 305 306 307 308 EntryNode<K,1)">309 310 311 312 313 314 315 316 317 318 }319 320 EntryNode<K,1)">321 322 EntryNode<K,1)">323 324 325 326 }327 328 329 330 331 332 333 334 containsKey(K key) { 335 V value = get(key); 336 337 338 339 340 containsValue(V value) { 341 :::遍历全部桶链表 342 .elements) { 343 :::获得当前桶链表第一个节点 344 EntryNode<K,1)"> element; 345 346 :::遍历当前桶链表 347 348 :::如果value匹配 349 (entryNode.value.equals(value)) { 350 :::返回true 351 352 } { 353 :::不匹配，指向下一个节点 354 entryNode = entryNode.next; 355 356 357 358 359 :::所有的节点都遍历了，没有匹配的value 360 361 362 363 364 size() { 365 .size; 366 367 368 369 isEmpty() { 370 371 372 373 374 clear() { 375 :::遍历内部数组，将所有桶链表全部清空 376 377 378 379 380 :::size设置为0 381 382 383 384 385 iterator() { 386 Itr(); 387 388 389 390 391 Iterator<EntryNode<K,1)">.iterator(); 392 393 :::空容器 394 iterator.hasNext()){ 395 396 397 398 :::容器起始使用"[" 399 StringBuilder s = 400 401 :::反复迭代 402 403 :::获得迭代的当前元素 404 EntryNode<K,1)"> iterator.next(); 405 406 :::判断当前元素是否是最后一个元素 407 408 :::是最后一个元素，用"]"收尾 409 s.append(data).append("]"410 :::返回 拼接完毕的字符串 411 s.toString(); 412 }413 :::不是最后一个元素 414 415 s.append(data).append(",1)">416 417 418 419 420 421 * 哈希表 迭代器实现 422 423 424 425 * 迭代器 当前节点 426 * 427 428 429 430 * 迭代器 下一个节点 431 432 433 434 435 * 迭代器 当前内部数组的下标 436 437 currentIndex; 438 439 440 * 默认构造方法 441 442 Itr(){ 443 :::如果当前哈希表为空，直接返回 444 .isEmpty()){ 445 446 447 :::在构造方法中，将迭代器下标移动到第一个有效的节点上 448 449 :::遍历内部数组，找到第一个不为空的数组插槽slot 450 451 :::设置当前index 452 i; 453 454 EntryNode<K,1)">.elements[i]; 455 :::找到了第一个不为空的插槽slot 456 457 :::nextNode = 当前插槽第一个节点 458 firstEntryNode; 459 460 :::构造方法立即结束 461 462 463 464 465 466 467 hasNext() { 468 469 470 471 472 next() { 473 .nextNode; 474 :::暂存需要返回的节点 475 EntryNode<K,1)">476 477 :::nextNode指向自己的next 478 .nextNode.next; 479 :::判断当前nextNode是否为null 480 481 :::说明当前所在的桶链表已经遍历完毕 482 483 :::寻找下一个非空的插槽 484 485 486 487 488 EntryNode<K,1)">489 :::找到了后续不为空的插槽slot 490 491 492 493 :::跳出循环 494 495 } 496 497 498 needReturn; 499 500 501 502 remove() { 503 504 505 506 507 :::获得需要被移除的节点的key 508 K currentKey = .currentNode.key; 509 :::将其从哈希表中移除 510 HashMap..remove(currentKey); 511 512 :::currentNode设置为null，防止反复调用remove方法 513 514 515 516 } 哈希表简单的测试代码:
1 class MapTest { 2 main(String[] args){ 3 testJDKHashMap(); 4 5 System.out.println("=================================================" 6 7 testMyHashMap(); 8 9 10 testJDKHashMap(){ 11 java.util.Map<Integer,String> map1 = new java.util.HashMap<>(1,212 System.out.println(map1.put(1,"aaa")); 13 System.out.println(map1.put(2,"bbb"14 System.out.println(map1.put(3,"ccc"15 System.out.println(map1.put(1,1)">16 System.out.println(map1.put(2,1)">17 System.out.println(map1.put(3,1)">18 System.out.println(map1.put(1,"111"19 System.out.println(map1.put(3,1)">20 System.out.println(map1.put(4,"ddd"21 System.out.println(map1.put(5,"eee"22 System.out.println(map1.put(6,"fff"23 System.out.println(map1.put(8,"ggg"24 System.out.println(map1.put(11,1)">25 System.out.println(map1.put(22,1)">26 System.out.println(map1.put(33,1)">27 System.out.println(map1.put(9,1)">28 System.out.println(map1.put(10,1)">29 System.out.println(map1.put(12,1)">30 System.out.println(map1.put(13,1)">31 System.out.println(map1.put(14,1)">32 33 System.out.println(map1.toString()); 34 System.out.println(map1.containsKey(135 System.out.println(map1.containsKey(1136 System.out.println(map1.containsValue("bbb"37 System.out.println(map1.containsValue("aaa"38 System.out.println(map1.size()); 39 System.out.println(map1.get(140 System.out.println(map1.get(241 System.out.println(map1.get(342 System.out.println(map1.remove(143 System.out.println(map1.remove(244 45 46 47 48 testMyHashMap(){ 49 com.xiongyx.datastructures.map.Map<Integer,String> map2 = new com.xiongyx.datastructures.map.HashMap<>(1,1)">50 System.out.println(map2.put(1,1)">51 System.out.println(map2.put(2,1)">52 System.out.println(map2.put(3,1)">53 System.out.println(map2.put(1,1)">54 System.out.println(map2.put(2,1)">55 System.out.println(map2.put(3,1)">56 System.out.println(map2.put(1,1)">57 System.out.println(map2.put(3,1)">58 System.out.println(map2.put(4,1)">59 System.out.println(map2.put(5,1)">60 System.out.println(map2.put(6,1)">61 System.out.println(map2.put(8,1)">62 System.out.println(map2.put(11,1)">63 System.out.println(map2.put(22,1)">64 System.out.println(map2.put(33,1)">65 System.out.println(map2.put(9,1)">66 System.out.println(map2.put(10,1)">67 System.out.println(map2.put(12,1)">68 System.out.println(map2.put(13,1)">69 System.out.println(map2.put(14,1)">70 71 System.out.println(map2.toString()); 72 System.out.println(map2.containsKey(173 System.out.println(map2.containsKey(1174 System.out.println(map2.containsValue("bbb"75 System.out.println(map2.containsValue("aaa"76 System.out.println(map2.size()); 77 System.out.println(map2.get(178 System.out.println(map2.get(279 System.out.println(map2.get(380 System.out.println(map2.remove(181 System.out.println(map2.remove(282 83 84 } 我们的哈希表实现是demo级别的，功能简单，也比较好理解，希望这能够成为大家理解更加复杂的产品级哈希表实现的一个跳板。在理解了demo级别代码的基础之上，去阅读更加复杂的产品级实现代码，更好的理解哈希表，更好的理解自己所使用的数据结构，写出更高效，易维护的程序。 本系列博客的代码在我的 github上：https://github.com/1399852153/DataStructures?，存在许多不足之处，请多多指教。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
