说一说HashMap的实现原理

[问答题]

说一说HashMap的实现原理

查看答案及解析

得分点

数组、链表、红黑树

参考答案

标准回答

在JDK8中，HashMap底层是采用“数组+链表+红黑树”来实现的。

HashMap是基于哈希算法来确定元素的位置（槽）的，当我们向集合中存入数据时，它会计算传入的Key的哈希值，并利用哈希值取余来确定槽的位置。如果元素发生碰撞，也就是这个槽已经存在其他的元素了，则HashMap会通过链表将这些元素组织起来。如果碰撞进一步加剧，某个链表的长度达到了8，则HashMap会创建红黑树来代替这个链表，从而提高对这个槽中数据的查找的速度。

HashMap中，数组的默认初始容量为16，这个容量会以2的指数进行扩容。具体来说，当数组中的元素达到一定比例的时候HashMap就会扩容，这个比例叫做负载因子，默认为0.75。自动扩容机制，是为了保证HashMap初始时不必占据太大的内存，而在使用期间又可以实时保证有足够大的空间。采用2的指数进行扩容，是为了利用位运算，提高扩容运算的效率。

加分回答

HashMap是非线程安全的，所以在多线程环境下，各线程同时触发HashMap的改变时，都有可能会发生冲突。所以，在多线程环境下不建议使用HashMap，可以考虑使用Collections将HashMap转为线程安全的HashMap，更为推荐的方式则是使用ConcurrentHashMap。

延伸阅读

通过如下HashMap源码理解它的数据结构：

// 数组
transient Node<K,V>[] table;

// 链表
static class Node<K,V> implements Map.Entry<K,V> {
    ...
    Node<K,V> next;
}

// 红黑树
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
}

通过如下HashMap源码理解它的结构变化：

// 默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量（2^30）
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 转为树的临界点
static final int TREEIFY_THRESHOLD = 8;
// 转链表的临界点
static final int UNTREEIFY_THRESHOLD = 6;
// 支持树结构的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;

编辑于 2021-09-15 10:28:39 回复(0)

小曾不会写代码

在jdk1.7之前HashMap是基于数组和链表实现的，而且采用头插法。

而jdk1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。采用尾插法。

HashMap默认的初始化大小为 16。当HashMap中的元素个数之和大于负载因子*当前容量的时候就要进行扩充，容量变为原来的 2 倍。（这里注意不是数组中的个数，而且数组中和链/树中的所有元素个数之和！）

注意：我们还可以在预知存储数据量的情况下，提前设置初始容量（初始容量 = 预知数据量 / 加载因子）。这样做的好处是可以减少 resize() 操作，提高 HashMap 的效率

HashMap是线程不安全的，其主要体现：

1.在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。

2.在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。

作者：代码界的小白
链接：https://www.nowcoder.com/discuss/800382?channel=-1&source_id=profile_follow_post_nctrack
来源：牛客网

追问：HashMap的put方法说一下。

回答：通过阅读源码，可以从jdk1.7和1.8两个方面来回答

1.根据key通过哈希算法与与运算得出数组下标

2.如果数组下标元素为空，则将key和value封装为Entry对象（JDK1.7是Entry对象，JDK1.8是Node对象）并放入该位置。

3.如果数组下标位置元素不为空，则要分情况

(i)如果是在JDK1.7，则首先会判断是否需要扩容，如果要扩容就进行扩容，如果不需要扩容就生成Entry对象，并使用头插法添加到当前链表中。

(ii)如果是在JDK1.8中，则会先判断当前位置上的TreeNode类型，看是红黑树还是链表Node

(a)如果是红黑树TreeNode，则将key和value封装为一个红黑树节点并添加到红黑树中去，在这个过程中会判断红黑树中是否存在当前key，如果存在则更新value。

(b)如果此位置上的Node对象是链表节点，则将key和value封装为一个Node并通过尾插法插入到链表的最后位置去，因为是尾插法，所以需要遍历链表，在遍历过程中会判断是否存在当前key，如果存在则更新其value，当遍历完链表后，将新的Node插入到链表中，插入到链表后，会看当前链表的节点个数，如果大于8，则会将链表转为红黑树

(c)将key和value封装为Node插入到链表或红黑树后，在判断是否需要扩容，如果需要扩容，就结束put方法。

发表于 2021-11-26 11:23:00 回复(0)