用比喻的方法讲解一下 java 中 hashmap 的底层原理

一、用比喻的方法讲解一下 java 中 hashmap 的底层原理

1、Java中的HashMap可以看作是一个盒子，这个盒子里面存放着很多抽屉。每个抽屉都有一个标签，用来表示抽屉里的物品。当我们要把一些物品放入盒子中时，我们首先根据物品的特征确定一个标签，然后把物品放入对应的抽屉里。

2、在HashMap中，标签被称为“键（key）”，物品被称为“值（value）”。当我们要将一个键值对放入HashMap时，首先会根据键的特征计算出一个哈希值（hash value），这个哈希值就相当于标签。然后，根据哈希值找到对应的抽屉，将键值对放入抽屉中。

3、但是，由于可能会有多个键的哈希值相同，这就相当于多个键要放入同一个抽屉中。为了解决这个问题，HashMap使用了链表（LinkedList）的数据结构。当发生哈希冲突时，新的键值对会被添加到链表的末尾。这样，在查找某个键的值时，首先会根据键的哈希值找到对应的抽屉，然后再在链表中查找对应的键值对。

4、当HashMap中的键值对数量逐渐增多时，链表可能会变得很长，从而导致查找效率下降。为了解决这个问题，Java 8引入了红黑树（Red-Black Tree）的数据结构。当链表中的键值对数量超过一定阈值时，链表会被转换为红黑树。这样，在查找键值对时，可以通过红黑树的特性进行快速查找，提高了HashMap的性能。

5、总结起来，HashMap的底层原理可以比喻为一个盒子，其中包含很多抽屉。每个抽屉上有一个标签，用来表示抽屉里的物品。当要放入一个键值对时，首先根据键的哈希值找到对应的抽屉，然后将键值对放入抽屉中。当发生哈希冲突时，会使用链表或红黑树的方式解决。这样，我们在需要查找某个键对应的值时，可以快速定位到对应的抽屉，然后再在链表或红黑树中查找。

二、hashmap底层实现原理

hashmap底层实现原理是SortedMap接口能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。

如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable

从结构实现来讲，HashMap是：数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的。

从源码可知，HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组。Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)，除了K，V，还包含hash和next。

HashMap就是使用哈希表来存储的。哈希表为解决冲突，采用链地址法来解决问题，链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。

如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。

三、hashmap底层实现原理是什么

HashMap的实现原理：首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了。

这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。

当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中。

HashMap的实例有两个参数影响其性能：

初始容量和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。

加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。在Java编程语言中，加载因子默认值为0.75，默认哈希表元为101。