数据结构之Map/Set讲解+硬核源码剖析（二）+https://developer.aliyun.com/article/1413571
2.其他
当然还有其他方法，这里仅作了解即可
2. 除留余数法--(常用) 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数： Hash(key) = key% p(p<=m),将关键码转换成哈希地址
3. 平方取中法--(了解) 假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对 它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分 布，而位数又不是很大的情况
4. 折叠法--(了解) 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和， 并按散列表表长，取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
5. 随机数法--(了解) 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数 函数。 通常应用于关键字长度不等时采用此法
6. 数学分析法--(了解) 设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某 些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据 散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如： 假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以 选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转(如 1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方 法。 数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均 匀的情况
哈希函数设置的越巧妙，越能减少哈希冲突，但无法避免哈希冲突
那如何解决哈希冲突呢？常用的方法有两种：开散列和闭散列
3.哈希冲突的解决
1.闭散列
也叫开放定址法，当遇到哈希冲突时，如果此时哈希表未满，则证明一定有下标未填充数据，可以将发生哈希冲突的数据填入到空位，所以闭散列的关键是寻找空位，寻找空位有两种方式：线性探测和二次探测
1.线性探测
所谓的线性探测就是从发生冲突的位置开始，依次向后寻找空位
- 先利用哈希函数获得元素的插入位置，
- 如果为空直接插入；不为空，进行线性探测
2.二次探测
线性探测是从发生冲突的位置依次向后寻找空位，可能会导致数据过于集中，为了避免这种情况，可以采用二次探测来寻找空位
研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不 会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情 况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容
无论是二次探测还是线性探测，都需要开辟大量的空间来解决哈希冲突，所以通过闭散列的方式来解决哈希冲突会导致空间利用率不高，更合理的解决哈希冲突的方式是开散列，也是Java中JDK的解决方式
2.开散列(重点)
1.概念
开散列是通过"哈希桶"的方式来解决哈希冲突的，所谓的哈希桶，就是一个特殊的数组，数组的每个元素都是链表
这样，就算发生了哈希冲突，即产生了相同的下标，不需要再去探测空位置，而是在当前位置插入，形成一个链表，搜索数据时需要先定位到下标，再去遍历下标位置对应的整个链表，知道找到要搜索的数据
注意：
如果同时满足数组的长度 > 64 && 链表的长度 > 8 此时性能就会下降，可以通过红黑树来提高性能
2.哈希桶的模拟实现
1.当存储的数据是整数(Key的数据类型为Integer)
前期准备：
// 哈希表实际上一个数组 数组的元素是Node 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[] arr; public int usedSize; public HashBuck() { arr = new Node[5]; }
1.search
寻找哈希表中是否存在某个元素，存在返回true，不存在返回false；
public boolean search(int key) { int index = key % arr.length; Node cur = arr[index]; while (cur != null) { if (cur.key == key) { return true; } } return false; }
2.put
向哈希表中插入数据 需要先判断是否已经存在要插入的元素 如果存在更新val；不存在，直接插入(哈希表中不能存放两个相同的key)
同时，随着哈希表中的数据增多，要去判断冲突因子的是否合理，当同时满足数组的长度 > 64 && 链表的长度 > 8时，需要重新更新哈希表的长度，来降低负载因子的大小，降低哈希冲突；更新长度需要重新哈希，因为可能发生数据的移动
// put方法 public void put(int key,int val) { int index = key % arr.length; Node cur = arr[index]; // 遍历整个链表 看是否已经存在相同的key值 while (cur != null) { if (cur.key == key) { cur.val = val; return; } cur = cur.next; } // 头插法 arr[index]其实就是链表的头节点 Node newNode = new Node(key,val); newNode.next = arr[index]; arr[index] = newNode; usedSize++; // 判断负载因子此时是否合理 if(loadFactor() >= 0.75) { resize(); } } private double loadFactor() { return usedSize*1.0 / arr.length; } private void resize() { // 扩大到原来的两倍 Node[] tmpArr = new Node[arr.length*2]; // 扩容之后 要进行重新哈希 for (int i = 0; i <arr.length ; i++) { Node cur = arr[i]; while (cur != null) { Node curNext = cur.next; int newIndex = cur.key % tmpArr.length; // 头插 cur.next = tmpArr[newIndex]; tmpArr[newIndex] = cur; cur = curNext; } } //数组是对象！！！ arr = tmpArr; }
3.get
返回关键码Key对应的value 如果不存在返回-1
// get public int get(int key) { int index = key % arr.length; Node cur = arr[index]; while (cur != null) { if(cur.key == key) { return cur.val; } cur = cur.next; } return -1; }
2.数据类型是引用类型
1.前提准备
创建person类
/** * 数据类型是引用类型 即Key是引用 * 建立引用类Person 与 与 id的映射关系 */ class Person { public String id; public Person(String id) { this.id = id; } // 存储的对象是一个一个人 key是一个引用类型 想要将类型转化为整数 并比较大小 重写方法 @Override public boolean equals(Object object) { if (this == object) return true; if (object == null || getClass() != object.getClass()) return false; Person person = (Person) object; return id == person.id; } @Override public int hashCode() { return Objects.hash(id); } }
// K,V都是泛型 一定要在类的声明中添加 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>[] arr; public int usedSize; public HashBuck2() { arr = (Node<K, V>[]) new Node[5]; }
2.put
对于Person类来说，不能直接让他%length来获取他的下标，只能通过hashCode来获取其hash值，再让hash值取%length，从而获取他的下标
// put在hash中插入数据 public void put(K key, V val) { // 先获取对应的hash值 int hash = key.hashCode(); int index = hash % arr.length; Node<K,V> cur = arr[index]; while (cur != null) { if(cur.key.equals(key)) { cur.val = val; return; } cur = cur.next; } Node<K,V> newNode = new Node<>(key,val); newNode.next = arr[index]; arr[index] = newNode; usedSize++; // 判断负载因子此时是否合理 if(loadFactor() >= 0.75) { resize(); } } private double loadFactor() { return usedSize*1.0 / arr.length; } private void resize() { // 扩大到原来的两倍 Node<K,V>[] tmpArr = new Node[arr.length*2]; // 扩容之后 要进行重新哈希 for (int i = 0; i <arr.length ; i++) { Node cur = arr[i]; while (cur != null) { Node curNext = cur.next; int newIndex = cur.key.hashCode() % tmpArr.length; // 头插 cur.next = tmpArr[newIndex]; tmpArr[newIndex] = cur; cur = curNext; } } //数组是对象！！！ arr = tmpArr; }
3.get
// get 根据key获得他的val public V get(K key) { int hash = key.hashCode(); int index = hash % arr.length; Node<K,V> cur = arr[index]; while(cur != null) { if(cur.key.equals(key)) { return cur.val; } cur = cur.next; } return null; }
4.测试
public static void main(String[] args) { Person person1 = new Person("123"); Person person2 = new Person("123"); HashBuck2<Person,String> hashBuck2 = new HashBuck2<>(); hashBuck2.put(person1,"lvzi"); // 输出相同的结果 因为Person中重写了equals和hashcode方法 只要内容相同 就认为他们是相同的且具有相同的hashcode值 // get方法就是根据hashcode方法得到hashcode System.out.println(hashBuck2.get(person1));// 输出lvzi System.out.println(hashBuck2.get(person2));// 输出lvzi }
注意：
1.在链表中插入数据时有两种方法，头插或尾插jdk1.8之前采用的是头插，1.8之后采用的是尾插
2.哈希表的所有方法的时间复杂度都是O(1),获取index，遍历链表，链表的长度一定是常数的，因为有loadFactor的调节，链表长度过长，会使用红黑树来调整
3.对于引用类型来说，要重写equals和hashCode方法；重写equals方法是因为在比较的时候需要通过内容来进行比较；重写hashCode方法，便于利用数字定位类，也便于我们进行存储
4.equals方法和hashCode方法往往是要同时重写的，这是因为在使用哈希表等数据结构时要保证搜索的一致性
- 如果两个对象通过equals比较返回true，则他们的hashCode值应该相同
- 如果两个对象通过equals比较返回false，则他们的hashCode值不必须一定不同，但为了检索的效率，一般设置为不同
equals方法和hashCode方法的区别
六.hashMap的一些源码讲解
1.成员变量讲解
// 默认容量是16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 // 最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; // 负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f;
以上三个都很好理解，下面看几个较为重要但又陌生的成员变量
// 树化条件 每个链表中的结点>=8 static final int TREEIFY_THRESHOLD = 8; // 解树化条件 static final int UNTREEIFY_THRESHOLD = 6; // 最小的树华条件 哈希表的容量最小是64 static final int MIN_TREEIFY_CAPACITY = 64;
2.构造方法
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }
为什么哈希表的容量一定要是2的次幂呢？主要有以下两方面原因:
- 效率性能方面：在建立映射的过程中，最重要的一步在于获取到要插入数据的下标，在上述的模拟实现中，我们采用的是 hash % arr.length()的方法，但还有另一种更快的方法，就是使用位运算，当哈希表的容量n为2的次幂时 ，hash % n == hash &(n-1),这两种求下标的方式是等价的，使用&运算，可以大大提高运算速度
- 哈希函数与桶的关系：使用hash &(n-1)这种方式来获取下标还可以使元素分布更加均匀，降低哈希碰撞的可能性
当n为2的次幂时(4,16,32,64......)时，n-1就是一个每个二进制位都为1的特殊二进制数(15--1111),再通过hash & (n-1)实际上是对hash的每一位都进行了&操作，这种运算等价于hash % n，但是运算效率更高，为什么等价呢？下面附上证明:
抹除高位，只保留低位就相当于减去高位中所有的2^n的倍数(字丑，见谅)
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
注意看，这是我们常用的构造方法，但是这里面只设置了负载因子，并没有给容量，但是我们却能够直接使用，这是为什么呢？答案在put方法的源码之中
public V put(K key, V value) { // 调用putVal方法 return putVal(hash(key), key, value, false, true); }
