gpt4 book ai didi

java - Java中HashMap的内部实现

转载 作者:行者123 更新时间:2023-11-30 01:59:47 25 4
gpt4 key购买 nike

我正在尝试创建 HashMap() 的数据结构在 java 。 HashMap 的最大工作时间为 N = 1000操作和键只能是正整数。我所做的如下:

class MyHashMap {
final ListNode[] nodes = new ListNode[1000];
// "put", "get" and "remove" methods which take
// collisions into account using "chaining".
}

决定我的新键值对在 nodes 中的位置我总是需要计算一个索引。我使用的功能:

 public int getIndex(int key) { return Integer.hashCode(key) % nodes.length;}

返回 0 之间的整数和nodes.length 。但是我如何自己用 Java 编写一个哈希函数,将整数映射到某个索引而不使用 Integer.hashMap(key) ?而且程序很好,我真的不需要代码。

最佳答案

散列 int 值的一个简单策略是乘以一个大常量。如果您不使用常量,则根据您的 key 分配,您可能会得到非常差的冲突率。仍然有可能获得较差的 key 分配,但对于真实数据来说这种可能性较小。

注意:除非您知道 key 不能为负数,否则应使用 Math.abs 来确保它为非负数。

static final int K = 0x7A646E4D; // some large prime.

public int getIndex(int key) {
return Math.abs(key * K % nodes.length);
}

更快的解决方案是放弃使用 % 使用乘法和移位。例如

public int getIndex(int key) { 
return (int) ((key * K & 0xFFFF_FFFFL) * nodes.length >>> 32);
}

它的作用是将key * K 转换为分数,并且比使用% 更快

关于java - Java中HashMap的内部实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53264218/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com