HASH表原理
大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。
具体如何做呢?大家是否有注意到前面说的话:“数组可以通过下标直接定位到相应的空间”,对就是这句,哈希表的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。
不知道说到这里,一些不了解的朋友是否大概了解了哈希表的原理,其实就是通过空间换取时间的做法。到这里,可能有的朋友就会问,哈希函数对key进行转换,取余的值一定是唯一的吗?这个当然不能保证,主要是由于hashcode会对数组长度进行取余,因此其结果由于数组长度的限制必然会出现重复,所以就会有“冲突”这一问题,至于解决冲突的办法其实有很多种,比如重复散列的方式,大概就是定位的空间已经存在value且key不同的话就重新进行哈希加一并求模数组元素个数,既 (h(k)+i) mod S , i=1,2,3…… ,直到找到空间为止。还有其他的方式大家如果有兴趣的话可以自己找找资料看看。
在java.util.HashMap中的关键代码:
Entry[] table;
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);
}
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
分享到:
相关推荐
hash join 原理和算法 1.Hash Join概述 2.Hash Join原理 3.Hash Join算法 4.Hash Join的成本
Hash表采用了数组加链表的结构,即一个数组元组中不再是存储单个元素,而是存储一个链表,就好比包租婆收租的时候,一个握把上面挂了一连串的钥匙一样。Hash表的引出是为了减少查询数据库操作所带来的时间问题,将...
GeoHash将二维的经纬度转换成字符串
就是java的散列表示意图 很清晰易懂 比枯燥额文字好多了
一致性Hash算法的原理及实现
Hash join算法的一个基本思想就是根据小的row sources(称作build input,我们记较小的表为S,较大的表为B) 建立一个可以存在于hash area内存中的hash table,然后用大的row sources(称作probe input) 来探测前面所建...
js单页hash路由原理与应用实战详解.docx
Hash join算法原理 详细讲述了oracle sql语句的连接方式 对于sql调优提高有很大帮助
Hash函数和数字签名 Hash函数和数字签名 Hash函数和数字签名
Hash表的时间复杂度为什么是O(1)
文档描述了Windows下LM HASH ,NTLM HASH生成原理和规则。 并利用Python脚本进行模拟。 详细描述了 挑战/响应模式(鉴权协议)的原理 详细描述了NTLM SMB通信流程 对内网渗透入门感兴趣的一定下载
信息安全的核心技术是应用密码技术。密码技术的应用远不止局限于提供机密性服务,密码技术也提供数据完整性服务。密码学上的散列函数(Hash Functions)就是能提供数据完整性保障的一个重要工具。
数据结构中介绍hash表与trie树的原理,图文并茂,一看就懂
oracle hash join算法原理
hash实现原理hash实现原理hash实现原理hash实现原理hash实现原理hash实现原理
Hash算法的介绍,属于课件形式,图文并茂介绍Hash的原理和应用。
官方
OracleHashJoin算法原理分享.pdf
相信找到这里的 ,geohash算法原理及实现方式应该也有所了解了。原代码了出自 邓星林博客 http://www.cnblogs.com/dengxinglin/archive/2012/12/14/2817761.html 自已找来,加上8个区的实现,加些注释和例子,测试...
linux 下hash_map的基本原理及使用,希望对大家有帮助。