哈希:内部如何运作？

Question

这听起来可能是一个非常模糊的问题,但事实并非如此.我在维基上经历过Hash函数描述,但理解它并不是很有帮助.

我正在寻找像Hashing这样相当复杂的主题的简单答案.这是我的问题:

1. 哈希是什么意思？它在内部如何运作？
2. 它遵循什么算法？
3. 有什么区别HashMap,HashTable和HashList？
4. "恒定时间复杂度"是什么意思？为什么哈希的不同实现会给出恒定的时间操作？
5. 最后,为什么大多数的面试问题Hash和LinkedList询问,有没有从测试受访者的知识,为任何特定的逻辑？

我知道我的问题清单很大但我真的很感激,如果我能够对这些问题得到一些明确的答案,因为我真的想了解这个主题.

Answer 1

1. 这是关于散列的一个很好的解释.例如,您希望存储字符串"Rachel",您将哈希函数应用于该字符串以获取内存位置.myHashFunction(key: "Rachel" value: "Rachel") --> 10.对于输入"Rachel",该函数可能返回10,因此假设您有一个大小为100的数组,您将"Rachel"存储在索引10处.如果要检索该元素,只需调用GetmyHashFunction("Rachel")它,它将返回10.注意,对于此示例键是"Rachel",值是"Rachel",但您可以使用该键的另一个值,例如出生日期或对象.您的哈希函数可能会返回两个不同输入的相同内存位置,在这种情况下,如果您要实现自己的哈希表,则可能会发生冲突,您可能需要使用链接列表或其他技术来处理此问题.

2. 以下是一些常用的哈希函数.良好的散列函数满足:每个键同样可能散列到n个内存插槽中的任何一个,而与任何其他键散列到的位置无关.其中一种方法称为除法.我们通过将k的余数除以n,将密钥k映射到n个时隙之一.h(k) = k mod n.例如,如果您的数组大小n = 100和你的关键是一个整数k = 15,然后h(k) = 10.

3. Hashtable是同步的,Hashmap不是.Hashmap允许将空值作为键,但Hashtable不允许.

4. 哈希表的目的是在添加和获取元素时具有O(c)恒定的时间复杂度.在大小为N的链表中,如果要获取最后一个元素,则必须遍历所有列表,直到获得它为止,因此复杂度为O(N).使用哈希表如果要检索元素,只需传递密钥,哈希函数将返回所需的元素.如果散列函数很好地实现,它将处于恒定时间O(c)这意味着你不必遍历存储在散列表中的所有元素.您将立即获得该元素.

5. 程序员/开发人员计算机科学家需要了解数据结构和复杂性=)

Answer 2

1. 散列意味着生成表示值的(希望)唯一数字.
2. 不同类型的值(Integer,String等)使用不同的算法来计算哈希码.
3. HashMap和HashTable是地图 ; 它们是unqiue键的集合,每个键都与一个值相关联.
   Java没有HashList类.哈希集是一组唯一值.
4. 从哈希表中获取项目是关于表的大小的恒定时间.
   对于被散列的值,计算散列不一定是恒定时间.
   例如,计算字符串的散列涉及迭代字符串,而不是关于字符串大小的常量时间.
5. 这些是人们应该知道的事情.

Answer 3

1. Hashing正在将给定实体(在java术语中 - 一个对象)转换为某个数字(或序列).哈希函数是不可逆的 - 即您无法从哈希中获取原始对象.在内部实现(java.lang.Object通过JVM获取一些内存地址).

2. JVM地址是不重要的细节.每个类都可以hashCode()使用自己的算法覆盖该方法.Modren Java IDE允许生成好的hashCode方法.

3. Hashtable和hashmap是一回事.它们是键值对,其中键是经过哈希处理的.散列列表和散列集不存储值 - 仅存储键.

4. 常量时间意味着无论哈希表(或任何其他集合)中有多少条目,通过其键查找给定对象所需的操作数是不变的.那是-1,或接近1

5. 这是基本的计算机科学材料,并且假设每个人都熟悉它.我认为谷歌已经指定哈希表是计算机科学中最重要的数据结构.

Answer 4

我将尝试简单解释散列及其用途.

首先,考虑一个简单的清单.此类列表上的每个操作(插入,查找,删除)都具有O(n)复杂性,这意味着您必须解析整个列表(或平均一半)才能执行此类操作.

散列是一种非常简单有效的加速方法:考虑我们将整个列表分成一组小列表.一个这样的小列表中的项目将有一些共同点,这个东西可以从密钥中推断出来.例如,通过列出名称,我们可以使用第一个字母作为质量,选择要在哪个小列表中查找.通过这种方式,通过按键的第一个字母对数据进行分区,我们获得了一个简单的哈希,它可以将整个列表拆分成~30个较小的列表,这样每个操作都需要O(n)/ 30次.

但是,我们可以注意到结果并不完美.首先,它们只有30个,我们无法改变它.其次,有些字母比其他字母更频繁地使用,因此设置用Y或Z将比设置小得多A.为了获得更好的结果,最好找到一种方法来分割大小相同的项目.我们怎么能解决这个问题？这是您使用哈希函数的地方.这是一个能够创建任意数量的分区的功能,每个分区的项目数大致相同.在我们的名字示例中,我们可以使用类似的东西

int hash(const char* str){
    int rez = 0;
    for (int i = 0; i < strlen(str); i++)
        rez = rez * 37 + str[i];
    return rez % NUMBER_OF_PARTITIONS;
};

这将确保非常均匀的分布和可配置数量的集合(也称为桶).