在教科书提到的Hash函数就是求模了。Java的hash函数是怎样的呢?先看代码:
/**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions. This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
hash对一个对象的hashCode进行重新计算,而IndexFor生成这个对象的index。
hash值重新计算,是为了防止质量低下的hashCode()函数实现。在hashMap数组长度中长度是初始长度的2倍。通过右移造成地位的数据尽量的不同。
而 在计算index上使用的是h&(length-1)的方法。简单而效率高。
看了Java的代码,自己在设计hash函数的时候,就有选择了。尽量使用位运算符,少使用+-*/%的运算符,这样可以提高hash的效率。
分享到:
相关推荐
HashMap内部采用数组和链表的方式存储数据,每个元素都包含键值对,通过hash函数将键映射到数组的索引位置,实现高效的查找和插入。 HashMap的性能优化策略。 HashMap在性能优化方面采取多种策略,如扩容机制、负载...
首先在阅读HashMap源码前,我们需要知道的: 一.数组:连续的存储结构,存储相同类型的数据。对于指定下标的查找,时间复杂度为o(1);对于定值的查找,需要遍历数组,时 间复杂度为o(n),对于有序数组,则可采用二...
1.1 HashMap的构造函数 首先我们来看一下HashMap的构造函数: /** * Constructs an empty {@code HashMap} with the specified initial * capacity and load factor. * * @param initialCapacity the initial ...
通过使用哈希表反转索引哈希函数SSF:简单求和功能PAF:多项式累加函数
现在很多的Java程序员都会把HashMap当作一个热门话题,我也来说一说Hashmap。 我假设你对HashMap感兴趣,另外我认为你已经了解了HashMap的基础,这里我不再赘述HashMap是个什么东东,如果对于你来讲HashMap还是一...
之所以把HashSet和HashMap放在一起讲解,是因为二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也是说HashSet里面有一个HashMap(适配器模式)。因此本文将重点分析HashMap。 HashMap实现了Map...
java1.7 HashMap用的是数组+链表实现的,同时采用的头插入法,存在死循环的问题 java1.8 HashMap用的是数组+链表+红黑树实现的,采用尾插法实现的,解决了死循环的问题,今天分析的就是1.8 // 初始容量为16 ...
hash = new HashMap<Object,Object>(); TreeMap<Object,Object> treeMap = new TreeMap<Object,Object>(); list.add("a"); list.add("b"); list.add("c"); hash.put(3, ...
Java中入HashMap等一些键值对应的结构,基本上都可以用hashCode()来查找值,接下来我们就来详解Java中用于查找对象哈希码值的hashCode()函数:
给定一个C语言函数,要求实现在java类中进行调用。 45.如何获得数组的长度? 46.访问修饰符“public/private/protected/缺省的修饰符”的使用 47.用关键字final修饰一个类或者方法时,有何意义? 48.掌握类和...
Hashtable和HashMap采用的hash/rehash算法都大概一样,所以性能不会有很大的差异。 12、final, finally, finalize的区别。 final 用于声明属性,方法和类,分别表示属性不可变,方法不可覆盖,类不可继承。 ...
18、两个对象值相同(x.equals(y) == true),但却可有不同的hash code,这句话对不对? 9 19、是否可以继承String 类? 9 20、以下二条语句返回值为true 的有: 10 21、当一个对象被当作参数传递到一个方法后,此方法可...
3、编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串,但要保证汉字不被截取半个,如“我ABC”,4,应该截取“我AB”,输入“我ABC汉DEF”,6,应该输出“我ABC”,而不是“我ABC+汉...
3、编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串,但要保证汉字不被截取半个,如“我ABC”,4,应该截取“我AB”,输入“我ABC汉DEF”,6,应该输出“我ABC”,而不是“我ABC+汉...
3、编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串,但要保证汉字不被截取半个,如“我ABC”,4,应该截取“我AB”,输入“我ABC汉DEF”,6,应该输出“我ABC”,而不是“我ABC+汉...
一文让你彻底理解 Java HashMap 和 ConcurrentHashMap 2018-07-25 分类:JAVA开发、编程开发、首页精华0人评论 来源:crossoverjie.top 分享到:更多0 前言 Map 这样的 Key Value 在软件开发中是非常经典的结构,常...
Hashtable和HashMap采用的hash/rehash算法都大概一样,所以性能不会有很大的差异。 12、final, finally, finalize的区别。 final 用于声明属性,方法和类,分别表示属性不可变,方法不可覆盖,类不可继承。 ...
java8 源码 参考 1.基础 1.集合框架 1.HashMap HashMap 是由链表和数组组合而成的基本数据结构 ,k-v 存储,允许null key 和null value 初始容量 1 << 4 16 扩容因子 0.75f 即 容量 * 扩容因子 ...
3、编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串,但要保证汉字不被截取半个,如“我ABC”,4,应该截取“我AB”,输入“我ABC汉DEF”,6,应该输出“我ABC”,而不是“我ABC+汉...
当一个key-value键值对传递给一个哈希函数的时候,经过哈希函数的计算之后,根据结果会把key-value键值对...同样,在hash index里面,哈希索引列会被传递给哈希函数做匹配(类似于java里面的HashMap的Map操作),匹配成