数据结构之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); }