Hashmap源码解析-哈希和散列表(1)

HashMap源码解读系列教程:

在了解HashMap的源码之前,我们必须对其中涉及的一些概念有所了解,这样才更佳顺利的解读jdk源码

什么是哈希?

哈希(hash)实际上是指一种采样算法。它可以将一大段数据映射变换成一段很小的数据。而这段小数据就代表着这个数据的特征。举一个例子,一个人是一个复杂的构成,包含了身高、体重、教育、家庭、文化等等信息,但是我们一般都给每一个人都“取一个名字”,那么“取名”就类比哈希(hash)。你喊“张三”和“李四”就知道对应的是哪一个人。比如MD5就是一种hash函数。

一般来说一个好的哈希算法需要满足以下2个特点。

  • 抵抗哈希碰撞的能力:也就是说不一样的数据取得同样的hash值的几率较小。
  • 放篡改的能力:给定一大段数据,即使只修改一点点,再次求hash应该得到不同的值。

什么是哈希碰撞?

哈希碰撞意味着不同的数据求到的哈希值是一样的。

什么是散列表?

在讲散列表之前我们需要回顾一下数组和链表的特点。

  • 数组
    数组是通过下标来访问的,访问任意一个元素的时间复杂度是O(1)。其原理是这样的,在数组内部只能存放相同类型的元素,这意味着每个元素的大小是固定的。假设你需要访问下标为10的元素,那么你仅仅只需要使用“10*元素大小”就能知道你要访问的元素在内存的偏移量,那么访问速度是非常快的。但是如果需要对数组的元素进行删改或者扩容,那么就涉及到大量元素的移动,很消耗性能。
  • 链表
    链表在内存中的地址是不连续的,他们每一个元素通过一个指针指向下一个元素。于是对于访问任意元素的复杂度是O(n),最坏的情况需要遍历到最后一个元素才能找到。但是对于删改或者扩容却是相当的友好的。

链表和数组都有各自的优缺点。我们不是小孩子,不愿意做取舍,那么有什么数据结构可以包括数组和链表两种数据结构的优点呢?散列表就是在这个时刻闪亮登场了,它既兼顾了快速访问的特点,在一定程度上,删改元素也效率也比较高。当然这样的数据结构就会比数组和链表要复杂得多。

散列表的底层是一个数组,数组里面可能存放的是内容元素,也有可能是存放链表或者红黑树。

HashTable-散列表

往散列表中存数据

当往散列表中存放数据【put(key,value)】时,会有以下流程:

  1. 我们会根据key来计算hash值。
  2. 让后根据hash值定位到数组中的某一个位置(比如数组的第2个index,具体算法后面会讲到)。
  3. 如果这个这个数组的index处是null,那么就直接存放在这个位置。
  4. 如果这个这个数组的index处已经有值了【哈希碰撞】,那么将这个值升级为链表,将新的元素加到链表的尾部。
  5. 如果这个这个数组的index处已经有链表了【哈希碰撞】,且链表长度超过了8,那么将这个链表升级为红黑树,并且将要保存的元素保存到红黑树中。

避免哈希冲突

避免哈希冲突有很多中方法,比如线性探测、二次探测、双重散列或者链表法。上面讲“往散列表中存数据”说的就是链表法。当碰到哈希相同的key,我们将数组中存放元素的升级为链表。至于红黑树是jdk1.8才引入的,为了避免链表过长时,查询效率退化成O(n),当元素大于某个阈值就会从链表升级为红黑树【时间复杂度O(logn)】,提高查询效率。但是正规的散列表不包含红黑树,所以jdk1.8中HashMap的散列表相当于是一个变种。

散列表的装载因子

一开始我们初始化散列表底层数组的长度都是有限的,那么使用一段时间之后空间变小,那么就极有可能发生哈希冲突。如果哈希冲突过多,那么会导致链表或者红黑树太大,降低查找效率。于是我们会想办法保持一定比例的空槽位,降低哈希冲突。这个比例就叫做装载因子。它的计算公式是“填入散列表的元素个数 / 散列表的长度”。当监控到当前的非空槽位的比例大于装载因子,那么就会触发散列表的扩容。这意味着散列表底层数组的长度会变大,空位会变多。当然扩容之后,所有的元素都要重新分配槽位,这里后面会继续讲到。

原文链接:https://www.jdkdownload.com/hashmap_1.html