Java源码集合类HashMap学习1

柔光的暖阳◎ 2022-07-12 08:53 188阅读 0赞

Java中集合类HashMap是存储键值(key,value)对为元素的集合，键和值都是以类类型来存储，通过键(key)来获得对应的值(value)。使用HashMap集合最大的一个优点是查询值(value)的速度快。

为什么集合HashMap查询值的速度快呢？这里就要涉及到HashMap的底层实现，用了数据结构哈希表(hash table)。对与哈希表的实现原理这里做个简单介绍，可以让我们从全局上了解HashMap的底层实现原理，这样更有利于我们知道为什么HashMap要这样实现。哈希表的底层其实就是一个数组，如下图所示：

![Center][]

假设要往这个哈希表存储这样一组键值对(key,value)数据：  
        ("China","中国")、

("USA","美国")、

("HK","香港")、

("Canada","加拿大")、

("France","法国")

根据键值求出它的一个哈希码也叫散列码(是一个整数)，通过调用一个求哈希码的方法，假设该方法是        hashCode()，比如：  
hashCode("China")=3214，  
        hashCode("USA")=4012，  
        hashCode("HK")=6123，  
        hashCode("Canada")=3214，  
        hashCode("France")=3214

求出的这些个整数：3214、4012、6123、3214、3214就是哈希码了，计算出的哈希码值不一定都是不同的值，当存储的数据量比较大的时候计算出相同的哈希码值也是很常见的。这里为了说明方便故意设计有三个相同的哈希码值3214。接下来，有这么个方法根据哈希码值求出这些哈希码值存储在数组中的下标，假设该方法为index()，比如：  
        index(3214) = 1,  
        index(4012) = 3,  
        index(6123) = 5,  
        index(3214) = 1,  
        index(3214) = 1,  
        这样就求出了这些键值对在数组中存储的下标：1,3,5,1,1。把这组数据依次存储到数组中具体的过程，如下图所示：

![Center 1][]

从图中可以看出，圈号G代表的存储元素("Canada","加拿大")它在数组中的下标和圈号A都是1，并且该位置已经被圈号A占了，那么是不是圈号G的元素就把圈号A覆盖了呢？显然不能这样处理，而是圈号A就会有一个引用指向下一个元素，所以圈号G就被放在了圈号A下面(A->G)，其实这个就是组成了一个链表。当然具体是A指向G，还是G指向A的下一个元素就要看具体的实现。圈号M存储的数组下标也是1，那么就放在了圈号G的下面，圈号G指向了圈号M，最终就成了如上图所示的数据结构。

上面说明如何存储键值对数据到哈希表中，那么我们如何根据键(key)值获取值(value)呢？比如：当要根据字符串"Canada"获取值"加拿大"的时候，先计算字符串"Canada"的哈希码如：3214，然后在用这个哈希码3214求出在数组中的下标如：1。用上图来说明这个查找的过程。求出了存储的数组下标1，那么先与第一个键值对元素也就是圈号A的键(key)值比较，字符串"Canada"与字符串"China"是否相等，显然是不相等的也就会继续与圈号A的下一个元素圈号G比较，很明显相等这样就找到了要查找的键值对元素。

以上就是简单介绍了哈希表数据结构的基本实现，想要了解详细的哈希表数据结构实现请看数据结构相关的书。

[Center]: /images/20220710/4acb7cb83c2640d883662547df79c714.png
[Center 1]: /images/20220710/0624cac4305c4302bfe4ffec94c50eb5.png