JAVA中的有序hash

绝地灬酷狼 2023-10-18 22:21 101阅读 0赞

## 一.hashMap与linkedHashMap ##

经过两篇文章的讨论，已经可以清楚的知道hashmap利用hash算法将数据均匀分布。这种分布是无序的，即放入顺序和读取顺序不一致。那么JAVA中有没有又是基于hash又是有序的数据结构喃？有！它就是——linkedHashMap。

hashMap：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70][]

linkedHashMap：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 1][]

## 二.如何实现有序 ##

linkedhashMap实现有序是使用了经典的一种数据结构——双向链表。

每个节点拥有前后指针，指向直接前驱，直接后继，尾节点的尾指针直接指向头节点。

节点在链表上的顺序就是插入顺序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 2][]

## 三.源码 ##

首先可以看到linkedhashmap继承了hashmap，也就是说它就是基于hashmap实现的。

![20190725140903387.png][]

不同的地方是，linkedhashmap的内部节点内基于hashmap的内部节点类多了前后指针。

![20190725141031123.png][]

linkedhashmap没有重写put方法，一个元素put进来，还是调用hashmap的put方法。

可以看到hashmap在put的时候分情况分别会调用几个方法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 3][]

这几个方法hashmap只给出了空实现，并且在注释上面清楚的写明，是为了linkedhashmap所留

![20190725143048901.png][]

然后linkedhashmap重写了这些方法，主要就是拿来操作前后指针，在put的时候指向前后节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 4][]

遍历的时候会发现linkedhashMap重写了Iterator，其实过程就是next next next......

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 5][]

至于构造方法中的那个标志位的作用就是拿来切换linkedhashmap的两种读取顺序而已。详细内容可以查询API。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190725135604818.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190725135641577.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190725140217996.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[20190725140903387.png]: https://img-blog.csdnimg.cn/20190725140903387.png
[20190725141031123.png]: https://img-blog.csdnimg.cn/20190725141031123.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190725142708132.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[20190725143048901.png]: https://img-blog.csdnimg.cn/20190725143048901.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2019072514315480.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20190725143858197.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pva2VyX1pKTg==,size_16,color_FFFFFF,t_70