HashMap的数据结构

待我称王封你为后i 2022-05-08 01:28 207阅读 0赞

前提：

主要数据结构：

[数据结构][Link 1]中有数组和链表来实现对数据的存储，但这两者基本上是两个极端。

### 数组 ###

数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；

### 链表 ###

链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。**链表**的特点是：寻址困难，插入和删除容易。

### 哈希表 ###

那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表。哈希表（(Hash table）既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。

哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法—— 拉链法，我们可以理解为“**链表的数组**” ，如图：

### 二叉树： ###

对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。

### **HashMap的数据结构：** ###

HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的即哈希表和红黑树。

### 结构组成： ###

首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。

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

![Center][]

参考：

[https://www.cnblogs.com/holyshengjie/p/6500463.html][https_www.cnblogs.com_holyshengjie_p_6500463.html]

[https://blog.csdn.net/tuke\_tuke/article/details/51588156][https_blog.csdn.net_tuke_tuke_article_details_51588156]

[Link 1]: http://lib.csdn.net/base/datastructure
[Center]: /images/20220508/795495b6e5144786b2079e5b9f705403.png
[https_www.cnblogs.com_holyshengjie_p_6500463.html]: https://www.cnblogs.com/holyshengjie/p/6500463.html
[https_blog.csdn.net_tuke_tuke_article_details_51588156]: https://blog.csdn.net/tuke_tuke/article/details/51588156