哈希表概述

哈希表概述

哈希值

万物都有哈希值

方法hashCode()就是返回一个对象的哈希值；这个方法属于Object类，Object类是万物的父类，所以也就是万物都有哈希值；

hashCode()返回的是int类型的值；

哈希表结构

哈希表的结构是对象数组+链表+二叉树的形式；

对象数组长度为16，元素下标为0-15，每个元素称之为哈希桶，也就是有16个哈希桶；

每个哈希桶的结构是链表加二叉树的形式；

哈希表存取数据

假如有个Object对象要存入哈希表中：

刚开使用**Object.hashCode()**得到一个int值的数据，然后int值%16(除16取余数)，得到的值为多少，就存入对象数组对应下标的哈希桶中，并放在链表第一个位置，当又一个对象进入该哈希桶，该对象就放在链表第二个位置，以此类推；

当一个哈希桶中存的对象大于8个时，链表就会自动变为二叉树的存储形式；

当哈希桶中对象个数减少到6个时，二叉树又会变成链表结构；

散列因子

初始时对象数组长度为16；但是当散列因子>=0.75时，对象数组长度会扩容两倍；

散列因子：就是目前存储了对象的哈希桶占目前所有哈希桶的比例，0.75就是指有75%的哈希桶存储了对象；

当扩容到两倍时：下一次就是除以32取余了(如果之前是除16取余)

HashMap存储数据：

HashMap存储的是键值(K V)的数据；

计算出K的哈希值，然后进行取余运算：(n-1) & hash：表示K的哈希值hash除以对象数组长度取余；

当该哈希桶没有数据，就创建一个新节点存入该键值对；

如果哈希桶已经有数据，就拿要存的数据的K和哈希桶里面的K一一比对，如果K一样，就用新的V覆盖旧V并返回旧V，如果K不一样则存存在最后的节点上；

当我们向HashMap中插入一个键值对时，会首先调用键对象的hashCode()方法，得到该键的哈希值。这个哈希值会被用来定位这个键值对在HashMap内部存储的位置。

然后，HashMap会根据得到的哈希值进行模运算，计算出一个数组下标。HashMap内部实际上是使用了一个数组来存放所有的键值对，这个数组的长度默认为16，并且会随着元素的增加而自动扩容。

接下来，根据计算出来的数组下标，我们会找到对应的位置。但是，这并不意味着我们就可以将键值对直接存放在这个位置，因为不同的键可能会产生相同的哈希值，这就会导致多个键值对被存放在同一个位置，这种情况被称为哈希冲突。

为了解决哈希冲突的问题，HashMap采用了链表和红黑树两种方式来存储同一下标的多个键值对。当我们插入第一个键值对时，会在对应位置创建一个链表节点，并将键值对存入。当我们继续插入具有相同哈希值的键值对时，会在链表的尾部添加新的节点。当链表的长度超过一定的阈值（默认为8），链表就会转化为红黑树，以提供更高效的查询性能。

当我们需要从HashMap中获取一个键对应的值时，会先计算出键的哈希值，然后根据哈希值找到对应的位置，然后在该位置上的链表或红黑树中查找对应的键值对。

这就是HashMap存储数据的基本流程，通过哈希化的方式，将键映射到一个固定大小的空间内，再通过链表或红黑树的方式来处理哈希冲突，使得HashMap能够在不同的场景下都能提供稳定的性能表现。

需要注意的是，虽然HashMap提供了高效的存取操作，但是它并不是线程安全的。如果在多线程环境下需要使用HashMap，建议使用Collections.synchronizedMap方法将其包装成线程安全的版本，或者使用ConcurrentHashMap等线程安全的数据结构。

HashMap以其高效、灵活的特性，成为了我们在编程过程中最常用的数据结构之一，深入理解其存数据的流程，对于我们更好地利用这一工具，提高程序的性能具有重要意义。