HashMap详解 Java [ 基础 ] ✅

大家好，欢迎来到IT知识分享网。

目录

✨探索Java基础   HashMap详解✨

总述

主体

1. HashMap的基本概念

2. HashMap的工作原理

3. HashMap的常用操作

4. HashMap的优缺点

5..jdk1.8对HashMap主要做了哪些优化呢？

1. 数据结构

2. 链表插入方式

3. 扩容（rehash）机制

4. 扩容时机

5. 散列函数

总结

常见面试题

常见面试题解答

1. HashMap的底层实现原理是什么？

2. 如何解决HashMap中的哈希冲突？

3. HashMap和Hashtable的区别是什么？

4. 在什么情况下HashMap会发生扩容？

5. 为什么HashMap不是线程安全的？如何实现线程安全的HashMap？

ConCurrentHashMap Put流程：

HashMap源码

1 put方法流程

2 扩容

3 get方法

✨探索Java基础   HashMap详解✨

总述

在Java中，HashMap 是一个常用的数据结构，它实现了Map接口，允许我们通过键值对的形式存储和快速查找数据。HashMap的底层是基于哈希表（hash table）的实现，它的高效性和灵活性使其在各种编程场景中广受欢迎。本文将详细介绍HashMap的原理、使用方法、优缺点，并提供一些常见的面试题。

主体

1. HashMap的基本概念

JDK1.7的数据结构是 数组 + 链表

说⼀下JDK1.8的数据结构吧： JDK1.8的数据结构是 数组 + 链表 + 红⿊树 。

HashMap是一个散列表，它存储键值对（key-value pairs），每个键对应一个唯一的值。HashMap不保证顺序，并且允许null值作为键或值。

import java.util.HashMap; public class Main { public static void main(String[] args) { HashMap<String, Integer> map = new HashMap<>(); map.put("one", 1); map.put("two", 2); map.put("three", 3); System.out.println(map.get("one")); // 输出: 1 } } 

2. HashMap的工作原理

HashMap使用哈希表来存储数据。键的哈希值通过hash()方法计算，然后通过哈希函数将哈希值映射到数组的索引位置上。通过链地址法（chaining）来解决哈希冲突，即在每个数组索引处存储一个链表（Java 8及之后版本采用红黑树以提高性能）。

public int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 

3. HashMap的常用操作

• 添加元素： 使用put()方法。
• 

插入流程：

• 获取元素： 使用get()方法。

  int value = map.get("two");

查找流程：

• 移除元素： 使用remove()方法。

  map.remove("three");

• 遍历元素：

  for (Map.Entry<String, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } 

4. HashMap的优缺点

优点：

• 快速查找： 平均时间复杂度为O(1)。
• 灵活： 可以存储不同类型的对象，允许null键和值。

缺点：

• 非线程安全： 多线程情况下需要手动同步。
• 不保证顺序： 插入顺序和遍历顺序可能不同。

5..jdk1.8对HashMap主要做了哪些优化呢？

1. 数据结构

• 变化：从数组 + 链表改为数组 + 链表或红黑树。
• 原因：当发生哈希冲突时，元素会被存储在链表中。如果链表过长，则转换为红黑树，将查找时间复杂度由 O(n) 降低至 O(logn)。

2. 链表插入方式

• 变化：从头插法改为尾插法。
• 说明：在 JDK 1.7 中，新元素被放置到链表头部；而在 JDK 1.8 中，遍历链表并将新元素放置到链表尾部。
• 原因：JDK 1.7 的头插法在扩容时可能导致链表反转，在多线程环境下可能会产生环状结构，而尾插法则避免了这一问题。

3. 扩容（rehash）机制

• 变化：采用更简单的判断逻辑来决定新位置。
• 说明：JDK 1.7 在扩容时需要重新计算每个元素的新哈希值以确定其在新数组中的位置；JDK 1.8 则通过更简化的逻辑直接确定新位置，通常是原索引或者原索引加上新增容量大小。
• 原因：这种改变提高了扩容操作的效率。

4. 扩容时机

• 变化：从先判断是否需要扩容再进行插入，变更为先执行插入操作，之后再判断是否需要扩容。
• 原因：这样可以减少不必要的扩容检查次数，尤其是在频繁插入但不经常达到扩容阈值的情况下。

5. 散列函数

• 变化：减少了散列函数的操作次数。
• 说明：JDK 1.7 的散列函数执行了四次位移和异或操作，而 JDK 1.8 只执行一次。
• 原因：尽管多次操作可能提供更好的分布性，但实际上边际效益不大，简化后的散列函数提高了计算速度且对于大多数应用场景来说足够有效。

总结

HashMap是Java中一个强大且高效的集合类，用于快速查找和存储键值对。理解其工作原理和常用操作对于提高编程效率和解决复杂问题非常有帮助。

常见面试题

1. HashMap的底层实现原理是什么？
2. 如何解决HashMap中的哈希冲突？
3. HashMap和Hashtable的区别是什么？
4. 在什么情况下HashMap会发生扩容？
5. 为什么HashMap不是线程安全的？如何实现线程安全的HashMap？

常见面试题解答

1. HashMap的底层实现原理是什么？

HashMap的底层是基于哈希表（hash table）实现的。它内部使用一个数组来存储元素，每个数组的元素被称为“桶”（bucket）。当我们向HashMap中插入一个键值对时，会先根据键的hashCode()方法计算出哈希值，然后通过哈希函数将哈希值映射到数组的索引位置上。HashMap通过链地址法（chaining）来解决哈希冲突，即每个桶中存储一个链表（Java 8及之后版本采用红黑树以提高性能）。

public int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 

2. 如何解决HashMap中的哈希冲突？

HashMap采用链地址法（chaining）来解决哈希冲突。具体方法是，每个桶中存储一个链表（或者在Java 8及之后版本中，当链表长度超过一定阈值时，会转换成红黑树），所有映射到同一索引位置的键值对都会存储在这个链表或红黑树中。

当插入一个新的键值对时，如果该键值对的哈希值映射到的索引位置已经存在其它元素，则会将新的键值对添加到该位置的链表或红黑树中。

3. HashMap和Hashtable的区别是什么？

• 线程安全性： Hashtable是线程安全的，所有方法都是同步的，而HashMap不是线程安全的，适用于单线程环境或通过外部同步来保证线程安全。
• null键和值： HashMap允许一个null键和多个null值，而Hashtable不允许null键和值。
• 性能： 由于Hashtable的方法是同步的，因此在单线程环境下性能比HashMap差。
• 遗产： Hashtable是基于较老的Dictionary类实现的，而HashMap是从Java 1.2开始作为Map接口的实现类。

4. 在什么情况下HashMap会发生扩容？

HashMap会在容量达到阈值（默认是当前容量的0.75倍）时发生扩容。扩容时，HashMap的容量会变为原来的两倍，并重新哈希已有的键值对，重新分配到新的桶中。扩容可以避免哈希冲突，保持HashMap的高效性。

5. 为什么HashMap不是线程安全的？如何实现线程安全的HashMap？

HashMap不是线程安全的，因为它的所有方法都不是同步的。在多线程环境下，多个线程同时修改HashMap的结构可能导致数据不一致或出现死循环。

要实现线程安全的HashMap，可以通过以下方法：

• 使用Collections.synchronizedMap(Map<K, V> m)方法： 这个方法返回一个线程安全的Map。

  Map<String, Integer> synchronizedMap = Collections.synchronizedMap(new HashMap<>());

• 使用ConcurrentHashMap： 这是Java提供的线程安全的Map实现，适用于高并发环境。它通过分段锁机制（Segmented Locking）来提高并发性能。

  ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();

ConCurrentHashMap Put流程：

具体：整个流程和HashMap⾮常类似，只不过是先定位到具体的Segment，然后通过ReentrantLock去操作⽽已，后⾯ 的流程，就和HashMap基本上是⼀样的。

1. 计算hash，定位到segment，segment如果是空就先初始化

2. 使⽤ReentrantLock加锁，如果获取锁失败则尝试⾃旋，⾃旋超过次数就阻塞获取，保证⼀定获取锁成功

3. 遍历HashEntry，就是和HashMap⼀样，数组中key和hash⼀样就直接替换，不存在就再插⼊链表，链表同 样操作

可见下图：

HashMap源码

1 put方法流程

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //判断数组是否未初始化 if ((tab = table) == null || (n = tab.length) == 0) //如果未初始化，调用resize方法 进行初始化 n = (tab = resize()).length; //通过 & 运算求出该数据（key）的数组下标并判断该下标位置是否有数据 if ((p = tab[i = (n - 1) & hash]) == null) //如果没有，直接将数据放在该下标位置 tab[i] = newNode(hash, key, value, null); //该数组下标有数据的情况 else { Node<K,V> e; K k; //判断该位置数据的key和新来的数据是否一样 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //如果一样，证明为修改操作，该节点的数据赋值给e,后边会用到 e = p; //判断是不是红黑树 else if (p instanceof TreeNode) //如果是红黑树的话，进行红黑树的操作 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //新数据和当前数组既不相同，也不是红黑树节点，证明是链表 else { //遍历链表 for (int binCount = 0; ; ++binCount) { //判断next节点，如果为空的话，证明遍历到链表尾部了 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是否为空（e值为修改操作存放原数据的变量） if (e != null) { // existing mapping for key //不为空的话证明是修改操作，取出老值 V oldValue = e.value; //一定会执行 onlyIfAbsent传进来的是false if (!onlyIfAbsent || oldValue == null) //将新值赋值当前节点 e.value = value; afterNodeAccess(e); //返回老值 return oldValue; } } //计数器，计算当前节点的修改次数 ++modCount; //当前数组中的数据数量如果大于扩容阈值 if (++size > threshold) //进行扩容操作 resize(); //空方法 afterNodeInsertion(evict); //添加操作时 返回空值 return null; }

2 扩容

//扩容、初始化数组 final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; //如果当前数组为null的时候，把oldCap老数组容量设置为0 int oldCap = (oldTab == null) ? 0 : oldTab.length; //老的扩容阈值 int oldThr = threshold; int newCap, newThr = 0; //判断数组容量是否大于0，大于0说明数组已经初始化 if (oldCap > 0) { //判断当前数组长度是否大于最大数组长度 if (oldCap >= MAXIMUM_CAPACITY) { //如果是，将扩容阈值直接设置为int类型的最大数值并直接返回 threshold = Integer.MAX_VALUE; return oldTab; } //如果在最大长度范围内，则需要扩容 OldCap << 1等价于oldCap*2 //运算过后判断是不是最大值并且oldCap需要大于16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold 等价于oldThr*2 } //如果oldCap<0，但是已经初始化了，像把元素删除完之后的情况，那么它的临界值肯定还存在， 如果是首次初始化，它的临界值则为0 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; //数组未初始化的情况，将阈值和扩容因子都设置为默认值 else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //初始化容量小于16的时候，扩容阈值是没有赋值的 if (newThr == 0) { //创建阈值 float ft = (float)newCap * loadFactor; //判断新容量和新阈值是否大于最大容量 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //计算出来的阈值赋值 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) //根据上边计算得出的容量 创建新的数组 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //赋值 table = newTab; //扩容操作，判断不为空证明不是初始化数组 if (oldTab != null) { //遍历数组 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; //判断当前下标为j的数组如果不为空的话赋值个e，进行下一步操作 if ((e = oldTab[j]) != null) { //将数组位置置空 oldTab[j] = null; //判断是否有下个节点 if (e.next == null) //如果没有，就重新计算在新数组中的下标并放进去 newTab[e.hash & (newCap - 1)] = e; //有下个节点的情况，并且判断是否已经树化 else if (e instanceof TreeNode) //进行红黑树的操作 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //有下个节点的情况，并且没有树化（链表形式） else { //比如老数组容量是16，那下标就为0-15 //扩容操作*2，容量就变为32，下标为0-31 //低位：0-15，高位16-31 //定义了四个变量 // 低位头 低位尾 Node<K,V> loHead = null, loTail = null; // 高位头 高位尾 Node<K,V> hiHead = null, hiTail = null; //下个节点 Node<K,V> next; //循环遍历 do { //取出next节点 next = e.next; //通过 与操作 计算得出结果为0 if ((e.hash & oldCap) == 0) { //如果低位尾为null，证明当前数组位置为空，没有任何数据 if (loTail == null) //将e值放入低位头 loHead = e; //低位尾不为null，证明已经有数据了 else //将数据放入next节点 loTail.next = e; //记录低位尾数据 loTail = e; } //通过 与操作 计算得出结果不为0 else { //如果高位尾为null，证明当前数组位置为空，没有任何数据 if (hiTail == null) //将e值放入高位头 hiHead = e; //高位尾不为null，证明已经有数据了 else //将数据放入next节点 hiTail.next = e; //记录高位尾数据 hiTail = e; } } //如果e不为空，证明没有到链表尾部，继续执行循环 while ((e = next) != null); //低位尾如果记录的有数据，是链表 if (loTail != null) { //将下一个元素置空 loTail.next = null; //将低位头放入新数组的原下标位置 newTab[j] = loHead; } //高位尾如果记录的有数据，是链表 if (hiTail != null) { //将下一个元素置空 hiTail.next = null; //将高位头放入新数组的(原下标+原数组容量)位置 newTab[j + oldCap] = hiHead; } } } } } //返回新的数组对象 return newTab; }

3 get方法

public V get(Object key) { Node<K,V> e; //hash(key)，获取key的hash值 //调用getNode方法，见下面方法 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; //找到key对应的桶下标，赋值给first节点 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //判断hash值和key是否相等，如果是，则直接返回，桶中只有一个数据（大部分的情况） if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { //该节点是红黑树，则需要通过红黑树查找数据 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); //链表的情况，则需要遍历链表查找数据 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }

觉得有用的话可以点点赞 (*/ω＼*)，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。