HashMap

哈希表 / 散列表

哈希表可以理解为数组的扩展或者关联数组，数组使用数字下标来寻址，如果关键字的范围较小且是数字的话，可以直接使用数组来完成哈希表，但是空间利用率极低。同时键也可能不是数字，所以人们使用一种映射函数(哈希函数)来将关键字映射到特定的域中。

  • 键(key) 又称为关键字。唯一的标示要存储的数据，可以是数据本身或者数据的一部分。
  • 槽(slot/bucket) 哈希表中用于保存数据的一个单元，也就是数据真正存放的容器。
  • 哈希函数(hash function)：将键(key)映射(map)到数据应该存放的槽(slot)所在位置的函数。
  • 哈希冲突(hash collision)：哈希函数将两个不同的键映射到同一个索引的情况。

与其他数据结构比较：

  • 数组：寻址容易，插入和删除困难
  • 链表：寻址困难，插入和删除容易
  • 与二叉树不同，哈希表中存储的数据是无序的，对于查找任意数据高效。二叉树查找某一范围的一些数据比较高效。

理想情况下，哈希表的插入和查找操作的时间复杂度均为O(1)，任何一个数据项可以在一个与哈希表长度无关的时间内计算出一个哈希值，然后在常量时间内定位到一个桶。

可以通过使用不同的哈希函数和冲突解决方案在时间和空间性能上做取舍。

使用哈希表的插入主要有如下两个步骤：

  1. 使用哈希函数将被查找的键转换为数组的索引。这个过程是将长度不同的字符串映射为固定长度的整数值。根据键的类型和哈希表的大小选择不同的哈希函数。

  2. 处理哈希冲突。因为键是所有任意长度的字符串，数量是无穷的，而哈希值长度固定的常数，数量是有限的，同时根据生日悖论，必然有不同的键映射到同一个哈希值，这就产生了哈希冲突。

处理哈希冲突，通常有两类方法：

  • Open Hashing 比如拉链法，是哈希桶（Bucket Hashing）的一种。碰到哈希冲突后，用链表去延展。所以有链表带来的优缺点。（因为开辟了新空间，所以叫 Open Hashing）。

  • Closed Hashing 比如线性探测法。哈希冲突后，并不会在本身之外开拓新的空间，而是继续顺延下去某个位置来存放，（因为依旧在同一个密闭的空间，所以叫 Closed Hashing），至于 Open Addressing 的意思是，相对于那种通过链表来开拓新空间，它是在本身地址上，另外找个位置。所以叫开地址。 常用的开地址法有探测（Probing），某些哈希桶（Bucket Hashing）等。

HashMap

Java 的 HashMap 也是一个哈希表。先分配（allocate）一定的内存位置，然后向这些位置插入数据。使用 Open Hashing 拉链法解决哈希冲突。

储存位置的确定： 把 key 经过 hash 之后得到的值，取余（真正的实现是使用的位操作），得到一个在长度范围内的下标。

HashMap 非线程安全，需要线程安全的话，使用 ConcurrentHashMap 。 LinkedHashMap 是 HashMap的一个子类，是带插入顺序的 HashMap。

构造方法：

// 构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap
HashMap()
// 构造一个带指定初始容量和默认负载因子 (0.75) 的空 HashMap
HashMap(int initialCapacity)
// 构造一个带指定初始容量和加载因子的空 HashMap
HashMap(int initialCapacity, float loadFactor)

底层实现是数组，数组的每一项都是一条链表 （Entry<K,V>中的 next ）（ UPDATE：Java8 中使用链表+红黑树）。其中参数 initialCapacity 就代表了该数组的长度。（实际 capacity 是 initialCapacity 向上取最接近的一个 「2的幂的数」） 容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，

负载因子是哈希表在扩容前可以达到多满的一种尺度（threshold = (int)(capacity * loadFactor);），它衡量的是一个哈希表的空间的使用程度，负载因子越大表示哈希表的装填程度越高，反之愈小。

对于使用链表法的哈希表来说，查找一个元素的平均时间是O(1+a)， 因此如果负载因子越大，对空间的利用更充分，元素多了，哈希冲突的可能性变大，链表变长，后果是查找效率的降低； 如果负载因子太小，那么链表的数据少，对空间造成严重浪费。

系统默认负载因子为 0.75，一般情况下我们是无需修改的。

插入 put

先 hash 元素的 key 计算 hash() ，再根据数组长度取余 indexFor(hash, table.length)，得到数组下标，

然后通过数组下标得到链表的第一个元素Entry<K, V>，同时开始通过 next 进行迭代。

判断每个Entry<K, V>的 hash 值（注意不是 key 的 hash 值）是否与当前要插入的这个元素 hash 值一样，如果一样，则覆盖，并返回旧值。

迭代完后如果还没有返回，则说明是新元素，那么把该元素插队存在链头。

扩容 resize

当达到负载因子设定的数量后，会创建新的数组代替已有数组。新数据长度是旧数组的 2 倍。resize(2 * table.length);

这个过程需要将所有元素重新 hash 计算，插入新的数组中，开销较大。（实际的实现中有优化）

取值 get

先 hash 元素的 key 计算 hash() ，再根据数组长度取余 indexFor(hash, table.length)，得到数组下标，

然后通过数组下标得到链表的第一个元素Entry<K, V>，同时开始通过 next 进行迭代。

判断每个 Entry<K, V> 的 key 是否与当前要获取的这个元素 key 一样，如果一样，则返回这个Entry<K, V>。

ArrayMap

Andoid 提供的 ArrayMap 的特性是减少内存使用。牺牲一些插入和删除的性能。比 HashMap 占用的内存少很多。比较适合 1000 以内的元素个数使用。

ArrayMap 内部使用两个数组。一个记录 key hash 后的顺序列表，另一个按照 key 的顺序记录 key-value 值。

SparseArray

Andoid 提供的这些稀疏数组，因为指定了数据类型，所以没有 HashMap 那样的自动装箱过程。