JAVA数据结构 & 哈希表 -HashSet and HashMap
引例
在讲这个部分之前，请试着去做一下下面这道题。
题：给定一串序列（char[] (小写字母)），要求你将其排序并且不能出现重复也不能有一个缺席。
没错，我们可以这么做：
char[] arr = new char[26]; //假设ch 为某个小写字母; arr[ch - 'a']++;
我们可以讲这个字母减掉’ ‘ a ’（即 97），这样a对应0，b对应1…
这样我们就只需要遍历一遍数组，只要不是’\u0000’(默认值),就打印or其他。
并且也可以快速知道对应字母的个数。
这样的思想就是“哈希思想”，把一个元素以特定的方法放进数组里，只要知道这个方法，就可以快速查找并且快速发现重复…
Set和Map的最大用处就是查找！
哈希的时间复杂度甚至达到了O(1)！
因为根据下标来找，太快了！
1. 哈希方法导致的冲突
细心的同学可能发现了，用同一个哈希方法的话，避免不了两个元素放在了同一个位置去了，那么我们就需要避免和解决。
1.1 冲突的避免（从整体减少冲突的次数）
这里要用到一个 负载因子常量的概念（其他地方可能有其他的说法）
这个负载因子就是哈希表中【已经放入的元素的个数 / 表最大容量】的最大值
一些实验数据事实表明：
哈希表越满越容易冲突
呈现出S型趋势
设计：
只需要让实际的负载因子时刻小于这个最大值，一旦大于等于这个最大值的时候，就让数组扩容。
也面临了另一个大问题，就是扩容后，需要重新将每个元素按照原本的哈希方法放进哈希表。
public static final double Load_FACTOR = 0.75;//一直处于七五分满
1
1.2 冲突的解决
1.2.1 闭散列
散列这个说法一些书籍仍在使用【哈希表的意思】
那么闭散列就是在顺序表内部解决这个问题
至于用顺序表是因为下标访问快
线性探测法
发现用哈希方法解析后的下标，已经被占用，那么从左往右探测，第一个空的就可以放上去
缺点很大：放的效率很低，取的时候效率也低，要找的那个位置不是我们要的数据，那么就要“线性探测”从左往右遍历找我们的数据。
并且我们很难去区分这个位置是否有元素，比如int[] 可能值就是0，引用类型也可能值就是null，怎么就能说明那个位置空了呢？
很容易达到负载值而需要重新扩容
这个方法很少用，最多出道题恶心人。
例如问，按照线性探测法找，需要多少步？
二次探测法
本质上跟【线性探测法】的思路是一致的，放在顺序表的其他空的位置。
但是这个方法是按照一个规律去实现的
Hi = (H0 + i2) % m【m为表的大小，H代表哈希值(后面会讲)】
Hi = (H0 - i2) % m【或者是这种】
【i】就是“跳跃的次数”，即第一次发现该位置有人，跳一次，此时 i为1
跳一次后发现位置还是有元素，再次跳一次，此时 i为2
注意：放置的时候发现没有元素，即 i为0
如下图所示（e代表元素element）：
这种方法是线性探测法的优化，加快了放置查找的速度
其他缺点依旧一个不落的继承
1.2.2 开散列（哈希桶）
也就是在顺序表“外”
如图所示，让数组的类型为“链表的节点”，遇到该位置已经被占用，就头插进去就好
用带头+尾插的技巧也是完全可以的，因为插入的时候都是要检测是否重复的，自然到达链尾很容易
有些地方用二叉搜索树，甚至高度平衡的二叉树【即红黑树】
如下图所示：
是否是就很像一个一个的“桶”
所以才叫哈希桶
2. 基础简单的HashSet的模拟
用简单的 int(基本数据类型)
如下图的大概模板
属性：
节点数组
已存放元素个数
负载因子最大值
方法：
构造方法
放置方法（重复则覆盖）
扩容重塑方法
计算负载因子方法
获取key键方法（这里可以认为是判断是否存在）
这里如果是Map，则对应返回的应该是键值对key对应的value值
public class HashBuck {//哈希桶法 static class Node { } public Node[] array; public int useSize; public static final double Load_FACTOR = 0.75;//"全局"常数 public HashBuck() { array = new Node[10]; } public void put(int key) { } private void resize() { } private double calculateLoadFactor() { } public boolean get(int key) { } }
2.1 属性
2.1.1 节点
//静态内部类 static class Node { public int key; public Node next; public Node(int key) { this.key = key; } } public Node[] array;
2.1.2 已存放元素个数以及实际负载因子
public int useSize; public static final double Load_FACTOR = 0.75;//"全局"常数
2.2 方法
2.2.1 构造方法
public HashBuck() { array = new Node[10];//默认大小为10 }
2.2.2 放置方法
哈希方法我并没有直接做一个方法出来，一般就是一条表达式而已
这里是 int index = key % array.length;【取模法是很常见的】
public void put(int key) { int index = key % array.length; Node cur = array[index]; //检测 while(cur != null) { if(cur.key == key) { return; }else { cur = cur.next; } } //头插 Node newOne = new Node(key); newOne.next = array[index]; array[index] = newOne; //已存放元素+1，并且计算是否超过负载因子最大值，若超过，则扩容重塑 useSize++; if(calculateLoadFactor() > Load_FACTOR) { resize(); } }
2.2.3 计算负载因子方法
private double calculateLoadFactor() { return (double) useSize / array.length; }
2.2.4 扩容重塑方法
只需要遍历节点数组【哈希表】，null一定代表没有数据
不是null的就将该链表遍历一遍，每一个键值重新放置
这里拿一个新的数组放的原因是，重新放置可能会放在前面也可能放置到后面，那么这个值等一下可能又会被遍历到。
private void resize() { //扩容两倍，当然可以其他倍数（系统为1.5倍，随后细说） Node[] newArr = new Node[array.length * 2]; //重塑 for (int i = 0; i < array.length; i++) { while(array[i] != null) { int index = array[i].key % newArr.length; Node cur = newArr[index]; Node newOne = new Node(array[i].key); if(cur == null) { newArr[index] = newOne; }else { // 尾插法 while(cur.next != null) { // cur = cur.next; // } // cur.next = new Node(array[i].key, array[i].val); newOne.next = cur; newArr[index] = newOne; } array[i] = array[i].next; } } //指向新的节点数组 array = newArr;
2.2.5 获取key键方法
public boolean get(int key) { int index = key % array.length; Node cur = array[index]; while(cur != null) { if(cur.key == key) { return true; } cur = cur.next; } return false; }
我在这里就不测试了
3. HashMap的模拟
在【2】的基础下，只需要让节点多一个成员，则多出一层“映射关系”，这就是Map映射
如下代码，大致与上面相似
key为自变量，不能重复，重复则覆盖（value值更改）
public class HashBuck { static class Node { public int key; public int val; public Node next; public Node(int key, int val) { this.key = key; this.val = val; } } public Node[] array; public int useSize; public static final double Load_FACTOR = 0.75;//"全局"常数
public HashBuck() { array = new Node[10]; } public void put(int key, int val) { int index = key % array.length; Node cur = array[index]; while(cur != null) { if(cur.key == key) { cur.val = val; return; }else { cur = cur.next; } } Node newOne = new Node(key, val); newOne.next = array[index]; array[index] = newOne; useSize++; if(calculateLoadFactor() > Load_FACTOR) { resize(); } } private void resize() { Node[] newArr = new Node[array.length * 2]; for (int i = 0; i < array.length; i++) { while(array[i] != null) { int index = array[i].key % newArr.length; Node cur = newArr[index]; Node newOne = new Node(array[i].key, array[i].val); if(cur == null) { newArr[index] = newOne; }else { // 尾插 while(cur.next != null) { // cur = cur.next; // } // cur.next = new Node(array[i].key, array[i].val); newOne.next = cur; newArr[index] = newOne; } array[i] = array[i].next; } } array = newArr; } private double calculateLoadFactor() { return (double) useSize / array.length; } public int get(int key) { int index = key % array.length; Node cur = array[index]; while(cur != null) { if(cur.key == key) { return cur.val; } cur = cur.next; } return -1; } }
4. 数据类型为引用类型
我们刚才用的是int[ ] ，如果是String类型，自定义类型呢？
那么这里就需要用到一个方法hashcode() ，这个方法可以获取到哈希值（引用类型的身份证），这样就可以进行取模运算了
如果是自定义类型，我们得自己重写hashcode()方法,String系统已经重写了
一定一定要重写equals()方法，否则我们认为相同的两个引用，哈希值也会不同
下面是泛型版本：
public class MyHashMap <K, V> { //如果用到泛型的话，记住要重写一些方法，如equals 和 hashCode //以及在特定位置补上自己的哈希方法 static class Node<K, V> { public K key; public V val; public Node<K, V> next; public Node(K key, V val) { this.key = key; this.val = val; } } public Node<K, V>[] array; public int useSize; public static final double Load_FACTOR = 0.75;//"全局"常数 public MyHashMap() { array = (Node<K,V>[])(new Node[10]); } public void put(K key, V val) { int index = key.hashCode() % array.length; Node<K, V> cur = array[index]; while(cur != null) { if(cur.key.equals(key)) { cur.val = val; return; }else { cur = cur.next; } } Node<K, V> newOne = new Node<>(key, val); newOne.next = array[index]; array[index] = newOne; useSize++; if(calculateLoadFactor() > Load_FACTOR) { resize(); } } private void resize() { Node<K, V>[] newArr = (Node<K,V>[]) (new Node[array.length * 2]); for (int i = 0; i < array.length; i++) { while(array[i] != null) { int index = array[i].key.hashCode() % newArr.length; Node<K, V> cur = newArr[index]; Node<K, V> newOne = new Node<>(array[i].key, array[i].val); if(cur == null) { newArr[index] = newOne; }else { // 尾插 while(cur.next != null) { // cur = cur.next; // } // cur.next = new Node(array[i].key, array[i].val); newOne.next = cur; newArr[index] = newOne; } array[i] = array[i].next; } } array = newArr; } private double calculateLoadFactor() { return (double) useSize / array.length; } public V get(int key) { int index = key % array.length; Node<K, V> cur = array[index]; while(cur != null) { if(cur.key.equals(key)) { return cur.val; } cur = cur.next; } return null; } }
数组的构建参考的是hashMap源码
下面是随便一个自定义类：
class student { char[] name; int id; int score; }
【Alt + insert】后点击这个东西,一路next就好了
我们也可以自己去决定“怎么样才算相等”，自己重写equals（）
