首页 > 到底什么是 hash,有什么作用,hashtable hashmap 又是什么,跟 hash 有很大关系吗?

到底什么是 hash,有什么作用,hashtable hashmap 又是什么,跟 hash 有很大关系吗?

如标题.
我看过网上的解释,都是很官方的答案,看不明白.明白的大神能不能用通俗的语言解释.小弟感谢啦


Hash 一般也可叫做散列,你可以把 Hash 简单的理解为将一个对象通过 hashCode() 方法映射为一个 int 类型的值,其中 hashCode() 是定义在 Object 中的,而 java 中所有的类都继承自 Object。
所以所有的类都有默认的 hashCode() 方法,你可以根据自己的需要去进行重写。


以你说的 HashMap 为例:HashMap 在 JDK 默认的实现是 数组+链表,也就是一个数组,数组中的每一个元素都是一个链表,假设数组为 array,链表为 list。

HashMap 是对 key 做出了散列处理,也就是求出了 key 所对应的一个 int 值。
比如说你声明了一个 HashMap<String, Object> 类型,如果你调用一次 map.put("key", object)。
那么就先调用 "key".hashCode() 得到一个 int,这个 int 就是 "key" 的哈希值,用得到的这个 int 类型的值余上 array 的长度,就得到了这个 object 在 array 中的位置。

但是,在实际的使用中,可能会出现一种情况就是两个不同的对象的哈希值可能是相同的,假设 "key1" 和 "key2" 得到了相同的哈希值,那么这个时候我们调用 map.put("key1", object1) 和 map("key2", object2) 他们通过上面的步骤算出来的哈希值是相同的,也就是他们在 array 中的位置是相同的,这个就叫做 散列冲突

所以这就是为什么 JDK 使用 数组+链表 的实现形式了。我们通过上面的步骤得到一个对象在 array 中的位置,如果他们的哈希值相同,但是他们不是同一个 String,那么我们就将后添加的这个 object 添加到 list 中;如果他们是同一个 String,那么我们就用新的 object 覆盖它在 list 中的上一个 object。

例如,对于 "key1" 和 "key2" 通过散列得到的在 array 中的位置是相同的,那么我们判断 "key1".equals("key2"),如果返回 true,我们使用 object2 覆盖 object1,如果 返回 false,我们将 object2 添加到 list 中。

所以上面调用的结果应该如下,其中 2 是 "key1" 和 "key2" 通过散列的出来的在 array 中的位置:

{
    list0:null,
    list1:null,
    list2:[object1, object2]
}

JDK 使用的这种叫做分离链接法,还有一种叫做平方探测发法。有兴趣的话可以去看看《数据结构与算法分析》这本书,好像在第 5 章。


Hash中文翻译为散列,其实就是用于表示事物特征的一串特征码。
事物和其Hash其实就像人和指纹的关系,人完整的相貌有眼鼻口舌手脚等等等等,而指纹就是一个能鉴别不同人之间的特征,所以可以理解问指纹就是人的Hash
Hash的用处很多,比如验证、加密等都可以用到Hash
用于验证这就无须赘述了吧,人可以通过指纹来验证,文件、对象等等都可以通过其自身的Hash来验证,比如国外的一些网站提供下载时,一般还会提供一份下载文件的Hash(算法各有不同),以帮助下载者验证下载的文件是否正确(文件可能因为网络错误或者中间者攻击而被篡改)。不过Hash提取的只是特征,就行指纹一样,虽然说难以找到指纹一样的人,但并不代表找不到,所以Hash还存在一种问题,就是Hash冲突,即两个不同的事务其采集的特征是一致的。这种情况下我们可以采用不同的Hash算法进一步加以比较,比如指纹相同再比较一下脚纹,不过最终的办法还是真正全身比较。
而正是因为Hash只提取了事物的部分信息,所以用于加密也是非常可靠的,就如通常网站都会采用Hash来对密码进行加密,其作用就是即使密码泄露,破解者也无法知道密码到底是什么,就好像你知道指纹,但你却难以找到拥有这个指纹的人是谁。

JavaHashMapHashTable都是通过Hash算法来实现高效Map的方式,其区别仅是一些细节限制方面有所不同,和Hash算法本身并没有什么关系。


呃,你可以把它看成一个DNA,每个生物的DNA都是不一样的(在这里请不要举双胞胎DNA一样的例子啦)。那么在计算机中,每个对象的Hash(DNA)都是不一样的。
Hashmap是一个数组和链表的结合体(在数据结构称“链表散列“)。
HashTable是比较古老的东西了..主要区别在于HashMap 允许空(null)键值(key)


hash 又称 哈希,是一类函数的统称,其特点是定义域无限,值域有限


好吧,通俗的,如何比较2个文件是否相同,2个文件可以完全读取到的情况下逐字节是可以的,一般本地文件与网络文件比较的是hash值,通过一定hash算法算出然后比较这个简单的hash就能比较文件。同理内存中的数据仍然可以算出hash值进行比较

【热门文章】
【热门文章】