哈希表（Hashtable），也叫散列表，是根据关键码值而直接进行访问的数据结构

原理：

​ - 关键码通过Hash函数映射到哈希表中一个位置

​ - 底层数据结构：数组 + 链表 + 红黑树

Map：key-value，key不重复

​ - HashMap（JDK1.8）：

HashMap是基于哈希表（数组+链表+红黑树）的Map接口的实现，以key-value的形式存储

HashMap底层实现是table数组，数组的每一项由Node构成的一条链表

HashMap扩容：当HashMap中的元素的数量 >= size * 负载因子，且key对应table数组 != null 时，HashMap进行扩容处理(大小为原数组容量2倍)

查找元素的时间复杂度：O(1)

新增元素的时间复杂度：

​ - O(1)：直接插入数组中

​ - O(logn)：查找红黑树中的值比较

​ - O(n)：查找链表中的值比较

Set：不重复元素的集合

HashMap是Java工程师实际工作中最常用的数据结构之一, 用于保存键-值对形式的数据.

常用的api有get(根据key获取一个元素的值), put(插入一个元素), containsKey(某个元素是否存在) , 以及HashMap的遍历等.

实现方式: 一个Node类型的数组作为散列表保存数据, 当发生hash冲突时采用拉链法处理冲突, 使用链表来保存冲突的元素, 但是当冲突的元素个数达到一定的阈值之后(默认为8), 会将链表转化成红黑树.

​ 这种作法的好处是当冲突元素数量比较少时, 遍历链表不影响查询性能,而且链表的插入操作是O(1), 所以兼顾了插入和删除;而当冲突元素数量比较多, 链表O(n)的时间复杂度会让查询操作比较耗时, 因此转化成红黑树, 提高查询性能.

为什么HashMap的容量大小必须是2的整数次幂?

​ HashMap扩容时是扩容成原来的两倍, 并且要求是2的整数次幂, 如果在创建时指定的容量不为2的整数次幂, 在创建时也会调整成大于该值的最小2的整数次幂

​ 这样做的目的是计算key的hash值后, 能够快速找到该hash值对应在散列表上的位置. 具体做法是容量减一, 然后与hash值按位与, 由于容量是2的整数次幂, 减一之后就会得到全为1的二进制码(如'11111111'), 然后与hash值按位与就能快速得到散列表的下标, 计算过程采用减法操作和位运算, cpu的计算效率最高。