时间戳

首页 > 解决方案 > Java中HashMap的内部实现

java - Java中HashMap的内部实现

问题描述

我正在尝试HashMap()在 Java 中创建 a 的数据结构。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)？程序也很好，我真的不需要代码。

标签： javahashmaphash-function

解决方案

散列int值的一个简单策略是乘以一个大常数。如果您不使用常数，则根据您的密钥分配，您可能会获得非常差的冲突率。仍然有可能获得较差的密钥分布，但是对于真实数据来说不太可能。

注意：除非您知道密钥不能为负数，否则应使用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变成分数并且比使用更快%

推荐阅读