数据结构.Java哈希代码和bucket大小.关系



Java哈希代码是一个整数(大小为2 pow 32)

当我们创建哈希表/哈希映射时,它会创建大小等于映射初始容量的bucket。换句话说,它创建了一个"初始容量"大小的数组

问题1.它是如何将键(java对象)的哈希代码映射到bucket索引的?2.既然hashmap的大小可以增长,那么hashmap的尺寸可以等于2 pow 32吗?如果答案是肯定的,那么明智的做法是拥有一个大小为2 pow 32的数组?

以下是当前源代码的链接:http://www.docjar.com/html/api/java/util/HashMap.java.html

您的问题的答案(部分)是针对具体实施的。

1) 请参阅代码。请注意,您关于initialCapacity如何实现的假设是不正确的。。。至少适用于Oracle Java 6和7。具体地说,initialCapacity不一定是散列映射的数组大小。

2) HashMap的大小是条目数,它可以超过2^32!我想你实际上是在谈论能力。HashMap数组的大小理论上限制为2^31 - 1(Java数组的最大大小)。对于当前的实现,MAX_CAPACITY实际上是2^30;请参阅代码。

3) "…有一个2^32大小的数组是明智的?"目前定义的Java是不可能的,尝试做一些不可能的事情是不明智的。

如果你真的在问Java中哈希表数据结构的设计,那么在普通大小的哈希表和巨大的哈希表的效率之间存在权衡;即具有明显多于CCD_ 9元素的映射。HashMap实现被调整为最适合正常大小的映射。如果您经常需要处理庞大的映射,并且性能至关重要,那么您应该考虑实现一个根据您的特定需求进行调整的自定义映射类。

Java数组的大小实际上仅限于Integer.MAX_VALUE元素,2^31-1。

HashMap使用两个数组大小的幂,所以它可能使用的最大值是2^31。你需要一个大的物理内存来实现这一点。

HashMap在执行简单的逐位and以获取bucket索引之前,会执行一系列移位和异或操作来减少一些冲突源。

最新更新