Java源码HashMap与HashSet解析

2019-11-06 07:13:46

字体：大中小

来源：转载

供稿：网友

HashSet与HashMap的关系用一句话概括为：披着羊皮的狼。其内部实现实际上是用了HashMap的实例，将具体实现委托给HashMap进行完成的。本文主要讲解部分HashMap的相关方法。

HashMap采用了拉链法解决hash冲突问题，一部分为数组，可以通过hash后的值找到该数组处的链表。另一部分是链表，通过map实体组成的链表前后相连组成链表。影响其性能的两个主要的参数主要是初始值和负载因子，初始值设置为16，负载因子默认为0.75。

主要方法

indexFor方法

求出该hash在数组中索引位置。通过该index即可找到该链表。

/* * 通过&求其映射的位置 * hash值映射的位置 */ static int indexFor(int h, int length) { return h & (length-1); }

put方法

前部分需要计算其hash值，然后根据hash值求出其索引值，根据索引值找到要进行查找的链表。进而对链表进行遍历，看是不是存在该key，存在则覆盖旧值，不存在则直接插入。

/* * 放入key和value * 如果当前有这个键值对的话，就直接覆盖并且返回旧的值 * 如果当前没有这个键值对的话，就返回null，将现在的值放进去 * * @see java.util.AbstractMap#put(java.lang.Object, java.lang.Object) */ public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.record access(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }

transfer方法

此方法主要是用于重新分配空间后将数据重新进行散列。每一个链表中的元素都要重新进行散列，不过每个元素的hash值不需要重新计算的，因为在插入的时候就已经确保了按统一的规则设定了。

/* * 重新计算当前hash值映射的位置 * 然后与newCapacity相&，由于重新计算了值，分配后的值不一定一样 * 需要重新组织链表结构 */ void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; // 插入的时候就已经计算出来其hash值了（hash方法），没必要再次计算了 int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }

removeEntryForKey方法

/* * 根据key删除 * */ final Entry<K,V> removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length); Entry<K,V> PRev = table[i]; Entry<K,V> e = prev; // 遍历链表 while (e != null) { Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; // 找到该节点 // 第一个节点 if (prev == e) // 将链表首节点删除 table[i] = next; else // 删除e节点，其pre节点的next指向了当前节点的next prev.next = next; e.recordRemoval(this); // 找到该key肯定是一个节点，只要找到即可返回 return e; } // 找不到继续向下遍历即可 // 前节点和next节点 prev = e; e = next; } return e; }

上一篇：8.java学习之静态方法

下一篇：从零开始来看一下Java泛型的设计