HashMap底层源码探究

HashMap底层源码探究

一、什么是哈希表

1.定义：散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。 2.哈希冲突：然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。 那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式，

二、HashMap的继承结构

从图中我们可以看到HashMap继承了 接口Cloneable，用于表明HashMap对象会重写java.lang.Object#clone（）方法 接口Serializeble，用于表明HashMap对象可以被序列化 HashMap同时继承了抽象类AbstractMap与接口Map，AbstrctMap相当于一个辅助类，对Map中的方法提供了一个基本实现，减少了实现Map接口的工作量，Map的一些操作在这里面已经提供了默认实现，后面具体的子类如果没有特殊行为，可以直接使用AbstractMap提供的实现。

三、HashMap的属性及默认值

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始化大小 16 static final float DEFAULT_LOAD_FACTOR = 0.75f; //负载因子0.75 static final Entry<?,?>[] EMPTY_TABLE = {}; //初始化的默认数组 transient int size; //HashMap中元素的数量 int threshold; //判断是否需要调整HashMap的容量

ps：HashMap的扩容操作是一项很耗时的任务，所以如果能估算Map的容量，最好给它一个默认初始值，避免进行多次扩容。HashMap的线程是不安全的，多线程环境中推荐是ConcurrentHashMap。

四、构造函数

HashMap()提供了四个构造函数：

HashMap() 构造一bai个具有默认初始容量 (16) 和默认加载因子du (0.75) 的空 HashMap(int initialCapacity) 构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap HashMap(int initialCapacity, float loadFactor) 构造一个带指定初始容量和加载因子的空 HashMap HashMap(Map<? extends K,? extends V> m) 构造一个映射关系与指定 Map 相同的新 HashMap

五、构造方法

1.put方法

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } //如果参数onlyIfAbsent是true，那么不会覆盖相同key的值value。如果evict是false。那么表示是在初始化时调用的 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //tab存放 当前的哈希桶， p用作临时链表节点 Node<K,V>[] tab; Node<K,V> p; int n, i; //如果当前哈希表是空的，代表是初始化 if ((tab = table) == null || (n = tab.length) == 0) //那么直接去扩容哈希表，并且将扩容后的哈希桶长度赋值给n n = (tab = resize()).length; //如果当前index的节点是空的，表示没有发生哈希碰撞。 直接构建一个新节点Node，挂载在index处即可。 //这里再啰嗦一下，数组下标index 是利用 哈希地址 & 哈希桶的长度-1，替代模运算 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else {//否则 发生了哈希冲突。 //e Node<K,V> e; K k; //如果哈希值相等，key也相等，则是覆盖value操作 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;//将当前节点引用赋值给e else if (p instanceof TreeNode)//红黑树暂且不谈 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else {//不是覆盖操作，则插入一个普通链表节点 //遍历链表 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) {//遍历到尾部，追加新节点到尾部 p.next = newNode(hash, key, value, null); //如果追加节点后，链表数量》=8，则转化为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //如果找到了要覆盖的节点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //如果e不是null，说明有需要覆盖的节点， if (e != null) { // existing mapping for key //则覆盖节点值，并返回原oldValue V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; //这是一个空实现的函数，用作LinkedHashMap重写使用。 afterNodeAccess(e); return oldValue; } } //如果执行到了这里，说明插入了一个新的节点，所以会修改modCount，以及返回null。 //修改modCount ++modCount; //更新size，并判断是否需要扩容。 if (++size > threshold) resize(); //这是一个空实现的函数，用作LinkedHashMap重写使用。 afterNodeInsertion(evict); return null; }

2、get方法

public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // 如果索引到的第一个Node，key 和 hash值都和传递进来的参数相等，则返回该Node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { //如果索引到的第一个Node 不符合要求，循环变量它的下一个节点。 if (first instanceof TreeNode) // 在树中get return ((TreeNode<K,V>)first).getTreeNode(hash, key); do {// 在链表中get if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }

3、remove方法

public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { // p 是待删除节点的前置节点 Node<K,V>[] tab; Node<K,V> p; int n, index; //如果哈希表不为空，则根据hash值算出的index下 有节点的话。 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { //node是待删除节点 Node<K,V> node = null, e; K k; V v; //如果链表头的就是需要删除的节点 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p;//将待删除节点引用赋给node else if ((e = p.next) != null) {//否则循环遍历 找到待删除节点，赋值给node if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } //如果有待删除节点node， 且 matchValue为false，或者值也相等 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p)//如果node == p，说明是链表头是待删除节点 tab[index] = node.next; else//否则待删除节点在表中间 p.next = node.next; ++modCount;//修改modCount --size;//修改size afterNodeRemoval(node);//LinkedHashMap回调函数 return node; } } return null; }

六、特点总结与适用场景

允许key与value值都为null值，HashMap以null作为key时，总是存储在table数组的0号索引位置上底层数据结构为哈希表，采用链地址法（数组+链表的形式存储数据）不保证其内部元素的顺序，而且随着时间的推移，同一元素的位置也可能发生改变（resize（扩容）情况）HashMap的初始默认值16，其容量必须是2的指数大小HashMap扩容：按照原容量大小的2倍扩容：2*table.lengthHashMap是一个线程非安全的，在多线程的情况下存在安全问题，所以不能在多线程中使用，那么如何才能使HashMap成为安全的呢？ 使用Collections.synchronizedMap（new HashMap（…））；通过这种方式可以得到一个线程安全的map。

HashMap的使用场景

数据统计时,Map存储的数据是键值对，key是统计的数，value是存入的数据次数，这样就能很好的完成数据统计。 eg：

public class HashMapTest { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<>(); Random random = new Random(); for (int i = 0; i < 100000; i++) { list.add(random.nextInt(1000)+1); } HashMap<Integer, Integer> hashMap = new HashMap<>(); Iterator<Integer> iterator = list.iterator(); while (iterator.hasNext()){ Integer key = iterator.next(); if (hashMap.containsKey(key)){ hashMap.put(key,hashMap.get(key)+1); } else { hashMap.put(key,1); } Iterator<Map.Entry<Integer, Integer>> iterator1 = hashMap.entrySet().iterator(); while (iterator1.hasNext()){ Map.Entry<Integer, Integer> next = iterator1.next(); Integer value = next.getValue(); Integer key1 = next.getKey(); System.out.println(key+" "+value+" "); } System.out.println(); } } }