什么是Hash（哈希表）？
① 先确定一个哈希函数：
hash (key) = key % capacity (通常会使用这种求余法，capacity是容量)
② 例子：
假如有一组数据集合：1，7，6，4，5，9 假设hash表容量为10
我们需要存入到哈希表中怎么存储？
我们将每个元素求到的hash数据存放到 hash表中得到
③ so？得出的结论
当我们查找元素的时候，只需要根据公式找到hashset的位置就可以直接找到元素的位置
，不必进行多次关键码的比较，搜索的速度比较快。
一般在查找一个元素时，要经过关键码的多次比较。
顺序查找的时间复杂度为 O（N）。平衡树查找的时间复杂度为树的高度，即O（logN）。
理想的搜索方法 : 不经过任何的比较，一次直接从表中得到搜索的元素。 很显然，顺序查找、平衡树查找都不是理性的，而哈希表是-------通过哈希函数是元素的存储位置与关键码之间能够建立起一一映射的关系，那么在查找的时通过该函数就可以直接找到该元素
哈希表插入/删除/查找的时间复杂度都是O（1）
冲突
① 概念（什么是冲突？）
不同的关键字通过 相同的哈希函数 计算出 相同的哈希地址，该现象称之为 哈希冲突 或 哈希碰撞。我们把 不同的关键码 而具有 相同哈希地址 的数据元素称为“ 同义词 ”。
② 冲突出现
- 出现冲突的一个重要原因：哈希函数设计不够合理。
- 常见哈希函数：(有很多很多，只列举俩)
1.直接定制法
(线性函数) Hash（key）= A*key + B
使用 场 景 ：需要事先知道关键字的分布情况，适合查找比较小且连续的情况
2.除留余数法
(上面的例子就是) Hash（key）= key%p （p接近地址数，但不大于地址数）
③ 冲突解决
- 两种解决方法：闭散列 和 开散列
闭散列（开放地址法）
- 思想：如果哈希表没有被装满，则为把key存放到冲突位置中的下一个。
探测方法：
1. 线性探测
直接插入到后面没有发生冲突的位置
缺陷：容易让产生冲突的元素堆积到一起
2. 二次探测
第一次发生冲突，重新通过哈希函数计算H(i) = （H0+i*i）% m（m是地址数）
一直计算，直至计算得到的哈希地址不存在冲突。
开散列（哈希桶）
思想: 使用数组+链表+红黑树的方式，数组里面存放链表的头节点
图示：
开散列代码实现//重点
// key-value 模型 public class HashBucket { private static class Node { private int key; private int value; Node next; public Node(int key, int value) { this.key = key; this.value = value; } } private Node[] array; private int size; // 当前的数据个数 private static final double LOAD_FACTOR = 0.75; public int put(int key, int value) { int index = key % array.length; // 在链表中查找 key 所在的结点 // 如果找到了，更新 // 所有结点都不是 key，插入一个新的结点 for (Node cur = array[index]; cur != null; cur = cur.next) { if (key == cur.key) { int oldValue = cur.value; cur.value = value; return oldValue; } } Node node = new Node(key, value); node.next = array[index]; array[index] = node; size++; if (loadFactor() >= LOAD_FACTOR) { resize(); } return -1; } private void resize() { Node[] newArray = new Node[array.length * 2]; for (int i = 0; i < array.length; i++) { Node next; for (Node cur = array[i]; cur != null; cur = next) { next = cur.next; int index = cur.key % newArray.length; cur.next = newArray[index]; newArray[index] = cur; } } array = newArray; } private double loadFactor() { return size * 1.0 / array.length; } public HashBucket() { array = new Node[8]; size = 0; } public int get(int key) { int index = key % array.length; Node head = array[index]; for (Node cur = head; cur != null; cur = cur.next) { if (key == cur.key) { return cur.value; } } return -1; } }
