我想创建一个大的HashMap,但put()性能不够好.有任何想法吗？
其他数据结构建议是受欢迎的,但我需要Java Map的查找功能:
map.get(key)
在我的情况下,我想创建一个包含2600万条目的地图.使用标准Java HashMap,在2-3百万次插入后,放置速率变得无法忍受.
此外,是否有人知道为密钥使用不同的哈希代码分发是否有帮助？
我的哈希码方法:
byte[] a = new byte[2];
byte[] b = new byte[3];
...
public int hashCode() {
int hash = 503;
hash = hash * 5381 + (a[0] + a[1]);
hash = hash * 5381 + (b[0] + b[1] + b[2]);
return hash;
}
我使用add的associative属性来确保相等的对象具有相同的哈希码.数组是字节,其值在0到51之间.值只在一个数组中使用一次.如果a数组包含相同的值(按任意顺序),则对象相等,而b数组则相同.所以a = {0,1} b = {45,12,33}和a = {1,0} b = {33,45,12}是相等的.
编辑,一些说明:
一些人批评使用哈希映射或其他数据结构来存储2600万个条目.我不明白为什么这看起来很奇怪.它看起来像是一个经典的数据结构和算法问题.我有2600万个项目,我希望能够快速将它们插入并从数据结构中查找它们:给我数据结构和算法.
将默认Java HashMap的初始容量设置为2600万会降低性能.
有些人建议使用数据库,在某些其他情况下这绝对是明智的选择.但我真的在问一个数据结构和算法的问题,一个完整的数据库会比一个好的数据结构解决方案过度而且速度慢得多(毕竟数据库只是软件,但会有通信和可能的磁盘开销).
有人可以向我解释静态HashMap #hash(int)方法吗？
生成均匀分布的哈希值背后的理由是什么？
/**
* 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 …在java中8 java.util.HashMap中我注意到一个变化来自:
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
到:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
从代码中可以看出,新函数是XOR低16位的简单函数,高16位保持高16位不变,而前一实现中的几个不同的位移相反,并且从评论中看,这在分配时效果较差散列函数的结果,在低位到较大位的冲突很多,但通过减少操作来节省CPU周期.
我在发行说明中看到的唯一一件事就是从链接列表到平衡树的变化以存储碰撞键(我认为这可能会改变计算好哈希的时间量),我特别感兴趣的是看到如果此更改对大型哈希映射有任何预期的性能影响.是否有关于此更改的任何信息,或者是否具有更好的哈希函数知识的任何人都知道此更改的含义可能是什么(如果有的话,我可能只是误解了代码)以及是否需要生成哈希迁移到Java 8时,以不同的方式编码以保持性能？
所以我在这里问了另一个相关的问题:带有雪崩效应的java字符串哈希函数,但我现在有一个不同的相关问题.
我在那个问题中建立的是String的hashCode()函数没有雪崩效应.这意味着,例如,如果我有字符串"k1","k2","k3",并且我在每个上调用hashCode(),则返回的值将是连续的.
现在,基于我对数据结构101的回忆,我的印象是这是一件坏事.因为假设HashMap通过算法选择桶,例如:
class HashMap {
private int capacity;
private int chooseBucket(String key) {
return key.hashCode() % capacity;
}
}
这意味着类似的密钥存储在连续的桶中,导致更高的冲突率,从O(1)降低大O查询时间到......谁知道有多糟糕......可能比O更差(log n ).
我在第一个问题中得到的答案类型是"这里不需要雪崩效应","它仅用于加密哈希函数",而且"字符串的hashCode实现很快,适用于小型哈希映射".
这让我很困惑.当它们很小时,所有数据结构都很快.Sun是否会提供一个适用于大型数据集的默认hashCode函数？那时候HashMap的表现真的很重要,不是吗？
或者,我错过了什么？请赐教.
Java doc hash方法说明,
检索对象哈希码并将补充哈希函数应用于结果哈希,以防止质量差的哈希函数.这很关键,因为HashMap使用两个幂的长度哈希表,否则会遇到低位不同的hashCodes的冲突.
我无法理解的是,
1)为什么HashMap使用2的幂长度哈希表？
在声明表时也说明了这一点:
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table;
为什么这个约束？
2)否则会遇到低位不相同的hashCode的冲突.意思？
我正在通过 Java 的 HashMap hash() 实现，如下所示
final int hash(Object k) {
// some checks
h ^= k.hashCode();
// 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);
// >>> is Unsigned right shift
}
我不确定为什么添加下面的代码，以及相同的好处是什么？
h ^= (h >>> 20) ^ …