HashMap
在Java世界里，HashMap应该是一个很基础的数据类型，Java的面试题里，似乎总喜欢问它的实现原理。
一、什么是HashMap
HashMap是一种集合，是Map的一种具体实现类。对外表现为采用键值对的方式存储数据。
二、HashMap的实现原理和存储结构
据说它查找效率很高。这跟它的存储结构有关。
HashMap的存储结构就是哈希表，一种称为拉链哈希表的哈希表。哈希（Hash），散列、杂凑之意，就是为了解决冲突的一种思想。哈希函数，得到一个计算结果，此结果是存放数据的地址。假如这个地址已经有数据占据，则需要另找一个新地址安放。冲突的情况下，新地址如何寻找，这是不同哈希表的区分依据。
哈希表有多种类型，如：线性哈希表，随机哈希表、溢出哈希表、拉链哈希表等。所谓拉链哈希表，就是有冲突的位置，会跟着一串争夺这个位置的链表。详细点说，就是某位置出现冲突，那么新来的数据也不用找别的地方了，大家都排着队指向这个位置。这个队列是链表，所以叫拉链哈希表。Java里的HashMap，存储结构就是拉链哈希表。
参考拙作：《哈希表》
数据存储下来，如何找到它呢？很简单，首先哈希函数算出地址，然后到该地址查找。没有冲突，直接找到返回。如果有链表，那么顺着链表找。
现在又有个问题。假如这条链表的元素很多，难道从头遍历一边吗？最坏的情况，寻找目标在链表的末端。HashMap的办法是，即当链表超过8时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。
红黑树本质上是二叉查找树。二叉查找树又叫二叉排序树、二叉搜索树，专门用于查找。节点是经过排序的：
1）左子树上的所有结点都小于根节点
2）右子树上的所有结点都不小于根节点
3）左右子树也满足上述两个要求。
参考拙作：《树》
红黑树又更进了一步，是自平衡的二叉查找树。不大好理解，只知道效率很高。“10亿数据中只需要进行10几次比较就能查找到目标”。
参考文章：
30张图带你彻底理解红黑树正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
