我最近几次遇到这些术语,但我很困惑它们是如何工作的以及它们何时被实施？
好吧,这样想吧.
如果你使用一个数组,一个简单的基于索引的数据结构,并用随机的东西填充它,当你用数据填充它时,找到一个特定的条目会变得越来越昂贵,因为你基本上必须从一端朝向另一端,直到找到你想要的那一个.
如果您希望更快地访问数据,您通常需要对数组进行排序并使用二进制搜索.然而,这在提高查找现有值的速度的同时,使得插入新值变慢,因为当您需要在中间插入元素时需要移动现有元素.
另一方面,哈希表具有一个相关的函数,它接受一个条目,并将其减少为一个数字,一个哈希键.然后将此数字用作数组的索引,这是存储条目的位置.
哈希表围绕一个数组,最初从空开始.Empty并不意味着零长度,数组以大小开始,但数组中的所有元素都不包含任何内容.
每个元素都有两个属性,数据和标识数据的键.例如,美国的邮政编码列表将是邮政编码 - >名称类型的关联.该功能减少了密钥,但不考虑数据.
因此,当您在哈希表中插入内容时,该函数会将键减少为一个数字,该数字用作此(空)数组的索引,这是存储数据(键和关联数据)的位置.
然后,稍后,您希望找到您知道密钥的特定条目,因此您通过相同的函数运行密钥,获取其哈希密钥,然后转到哈希表中的特定位置并在那里检索数据.
该理论认为,将您的密钥减少到哈希密钥(该数字)的函数在计算上比线性搜索便宜得多.
典型的散列表没有可用于存储的无限数量的元素,因此数量通常会进一步减少到适合数组大小的索引.一种方法是简单地将索引的模数与数组的大小进行比较.对于大小为10的数组,索引0-9将直接映射到索引,索引10-19将再次映射到0-9,依此类推.
某些键将缩减为与哈希表中现有条目相同的索引.此时,直接比较实际密钥,所有规则与比较密钥的数据类型(例如,正常字符串比较)相关联.如果存在完全匹配,则要么忽略新数据(它已经存在),要么覆盖(替换该键的旧数据),或者添加它(多值哈希表).如果没有匹配,这意味着尽管散列键是相同的,但实际的键不是,您通常会找到一个新的位置来存储该键+数据.
碰撞分辨率有很多实现,最简单的就是转到数组中的下一个空元素.这个简单的解决方案还有其他问题,因此找到正确的解析算法也是哈希表的一个很好的练习.
如果Hashtables完全填满(或接近),它们也会增长,这通常是通过创建新大小的新数组,再次计算所有索引,并将项目放入新数组中来实现的.位置.
将键减少到数字的功能不会产生线性值,即."AAA"变为1,然后"AAB"变为2,因此散列表不按任何典型值排序.
有可用的一个很好的维基百科文章的题目为好,在这里.
lassevk的答案非常好,但可能包含太多细节.这是执行摘要.我故意省略某些相关信息,您可以在99%的时间内安全地忽略这些信息.
在99%的情况下,散列表和散列映射之间没有重要区别.
认真.它是一个神奇的数据结构,几乎可以保证三件事.(也有例外.你可以在很大程度上忽略它们,虽然有一天学习它们可能对你有用.)
1)哈希表中的所有内容都是一对的一部分 - 有一个键和一个值.您通过指定要操作的密钥来输入和输出数据.
2)如果您通过哈希表上的单个键执行任何操作,则速度非常快.这意味着put(key,value),get(key),contains(key),和remove(key)都非常快.
3)通用哈希表在执行#2中未列出的任何操作时失败!("失败",我们的意思是他们非常缓慢.)
当他们的魔法符合我们的问题时,我们使用哈希表
例如,经常使用哈希表来缓存 - 例如,假设我们在一所大学有45,000名学生,而某些流程需要保留所有这些学生的记录.如果您经常按ID号引用学生,那么ID => student缓存非常有意义.您正在为此缓存优化的操作是快速查找.
当您不想进行整体操作并更改对象本身时,哈希对于存储数据之间的关系也非常有用.例如,在课程注册期间,能够将学生与他们正在学习的课程联系起来可能是个好主意.但是,无论出于何种原因,您可能不希望Student对象本身知道这一点.studentToClassRegistration当你做任何你需要做的事情时,使用哈希并保持它.
它们也是数据结构的一个相当不错的首选,除非您需要执行以下操作之一:
迭代元素.散列表通常不能很好地进行迭代.(通用的,即.特定的实现有时包含链接列表,用于使迭代对它们的吸收较少.例如,在Java中,LinkedHashMap允许您快速迭代键或值.)
排序. 如果你不能迭代,排序也是一种皇家的痛苦.
从价值到关键.使用两个哈希表.相信我,我只是为你节省了很多痛苦.
京公网安备 11010802040832号 | 京ICP备19059560号-6 