上一篇博主写了关于HashMap和Hashtable的区别与联系:
本篇博主将从浅入深地解读HashMap源码,学习一下被JDK收录的大神们写的代码思路~~
1.哈希表:基于数组的高效查找衍生出来的数据结构
2.哈希函数:将任意的key转为数组索引的函数、映射。将任意key映射为数组索引。
3.哈希冲突:不同的key经过hash函数的运算竟然得到了相同的数字 如: f(x1) = f(x2) => x1 != x2 【f(x)为hash运算】
4.开散列:在冲突的数组索引处转为链表实现。所有不同的key映射到数字索引的元素都在同一个链表存储。
若某个数组的索引位置冲突非常严重,哈希表查找有可能退化为链表遍历。
解决方案:
5.闭散列(二次探测)(再哈希):
6.负载因子(loadFactor): 表示当前哈希表最多的有效元素个数 / 哈希表长度
如:
int[] data = new int[16];
loadFactor = 0.75f;
data.length * loadFactor = 12; //有效的元素个数最多为12个元素,超过这个个数,哈希表就会扩容
小技巧:
判断一个字符串中某个字符出现的次数。str只是由小写字母组成,一共26个小写字母。
int[] freq = new int[26]; //char -> int
c - a => int a = ‘c’ - ‘a’ = 2
存储字符c出现几次,字符c一定出现在freq[c - ‘a’] => 唯一的位置 char c = ‘a’ => freq[0] ++ ‘a’ -> 0 哈希函数 char c = ‘b’ => freq[1] ++ ‘b’ 出现一次
不同freq索引就映射了不同的小写字母,一一对应。
hashCode()与equals()都是Object类的方法,而在把自定义的类当作Key传入HashMap中的时候,会根据自定义类重写的这两个方法来解决hash冲突。
只要是不同的对象原则上都会返回不同的整数。
一般来说这个方法用于比较两个对象是否相等,Object中的这个方法比较的是两个对象的地址是否相等,我们可以自己重写这个方法来实现根据何种属性判断是否相等。
通常有必要在重写hashCode方法时重写该方法,以便维护hashCode方法的通用规定,规定相等的对象必须具有相等的哈希码。
HashMap中Key的值是唯一的,所以HashMap会根据自定义的类中的equals方法来判断是否为同一个对象,如果此时HashMap又put进来一个相同的对象,那么HashMap中不会新增一个新的键值对,而是把这个Key对应的Value值更改。
现定义一个学生类:
class Student{
int age;
String name;
}
此时要将Student对象存储到HashMap的key上,会:
equals相同的两个对象,就认为是同一个对象,哈希表中的这个对象有且只能有一个。
自定义对象作为Key的唯一性,就是通过equals方法保证的。
拓展:equals相同的两个对象,hashCode是否相同?反之如何?
前者必须相同,后者不一定相同。
所以只有equals和hashCode都相同的对象才是唯一的对象。
这篇文章是HashMap的一些前置知识,下一篇博主将深入HashMap源代码,分析HashMap是如何设计的,它的存储逻辑以及如何解决冲突的。希望能帮到大家~~