【澳门新葡亰】澳门新葡亰网址

国内更专业
澳门新葡亰

流失-问答丨如何理解哈希表的工作原理?

  哈希来自英文hash的翻译。其实恰如其分应该叫散列。散列的目的就是找到一个函数能够将一堆数字均匀分布在一维数组里。理想状态大家存储的位置是不同的,否则哈希函数比较糟糕。但是当两个数字经过一次哈希发现存在同一个数组里,还会二次哈希把他存在另外一个不同地方,这就是所谓双哈希。但是影响哈希存储的最关键因素是数组大小,当足够大大家发生碰撞机会比较少,这就是为什么内存数据库,key值达到内存70%就要扩容。刚才看到楼上说的太简单而且概念有些错误忍不住发表两句。我们很少会用到数组加链表方式,因为查询不稳定。基本通过空间换时间才能达到大o常数效率

  哈希表是根据关键值(key)来直接访问目标值(value)的一种数据结构。其特点就在于能够快捷的实现信息的查询和检索。

  比如我们在手机中存放的通讯录就是用哈希表来实现的,即我们输入一个联系人的姓名,就能返回相应的电话号码。用哈希表实现的过程就是,将联系人姓名的字符通过一个哈希函数,映射成一个整数(哈希码),然后根据哈希码来索引出电线,就表示是在存储位置为5,因此我们就能直接取出该位置的值,并返回结果。

  那么实现哈希表的关键就在于哈希函数的构建,也就是如何建立一个合适的索引来满足如下条件:

  第一个条件意味着哈希函数必须是确定性的;第二个条件则要求不能出现哈希冲突。当两个或更多个键产生相同的哈希码时就会发生冲突(hash collisions)。

  比如我们现在考虑建立一个简单的哈希表来查询年龄,{Jim:5, Davis:7, Taylor:12, Bob:3},如果我们选择哈希函数为输入键值的字符个数。那么在建立哈希表时,就讲Jim存放在位置3处,Jack存放在位置4处。而这样的话Jim和Bob的存储位置就会发生冲突,不符合哈希函数的要求。但是如果我们将哈希函数替换为首字母顺序存放,在这个数据中就没有哈希冲突了。

  然而万一无法避免哈希冲突的话,我们可以用链接和线性探测的方法来避免哈希值发生碰撞。

  链接就是将发生冲突的键值直接链接在链表的尾部;线性探测则是,如果在位置i处发生冲突,那么就检查i+1处是否为空,为空的话就将冲突键值放入其中,否则继续检查下一个。

  谢邀。这个问题很有趣,哈希(Hashing)是一种用于从一组相似对象中唯一标识特定对象的技术。

  在图书馆中,每本书都被分配了一个唯一的编号,可用于确定有关图书的信息,例如图书馆中的确切位置或已发给图书的用户等。

  假设您有一个对象,并且您想为其分配一个键以便于搜索。 要存储键/值对,您可以使用一个简单的数组,如数据结构,其中键(整数)可以直接用作存储值的索引。 但是,如果密钥很大并且无法直接用作索引,则应使用哈希(Hashing)。

  在哈希中,通过使用哈希函数将大键转换为小键。 然后将这些值存储在称为哈希表的数据结构中。 哈希的想法是在数组中统一分配条目(键/值对)。 为每个元素分配一个键(转换键)。 通过使用该键,您可以在O(1)时间内访问该元素。 使用密钥,算法会计算一个索引,该索引可以找到或插入条目的位置。

  在此方法中,哈希与数组大小无关,然后通过使用模运算符(%)将其缩减为索引(介于0和array_size - 1之间的数字)。

  关联数组:哈希表通常用于实现许多类型的内存表。 它们用于实现关联数组(索引是任意字符串或其他复杂对象的数组)。

  数据库索引:哈希表也可以用作基于磁盘的数据结构和数据库索引(例如在dbm中)。

  高速缓存:哈希表可用于实现高速缓存,即用于加速对数据的访问的辅助数据表,其主要存储在较慢的介质中。

  对象表示:一些动态语言(如Perl,Python,Java和Ruby)使用哈希表来实现对象。

分享:

评论

无法在这个位置找到: ajaxfeedback.htm