blocks|key|2821993|text|我认为你混淆了术语，也因为思考桶而使事情复杂化。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2821994|让我们设想一个哈希表，它是作为长度为a的n数组实现的。让我们想象一下，我们有n可能的键和一个完美的哈希函数H，它将每个键k映射到a中的唯一索引i。|offset|length|style|CODE|2821995|让我们通过将a中的每个值设置为nil来初始化哈希表。|2821996|通过将值放在数组中的适当位置，我们可以将键值对(k1,+v1)插入到哈希表中：|2821997|a[H(k1)]+=+v1|code-block|syntax|javascript|2821998|现在，假设稍后我们忘记了k1是否在哈希表中，我们希望检查它是否存在。要做到这一点，我们只需查找a[H(k1)]并查看是否存在任何值，即a[H(k1)]+!=+nil。这显然是一个固定时间的查找。|2821999|但是，如果我们想看看v1，甚至是其他一些v2在我们的哈希表中的位置呢？这并不容易，因为我们没有将vi映射到数组中某个位置的函数。它可以与任何密钥相关联。因此，查看表中是否存在该数组的唯一方法是扫描整个数组，检查每个值：|2822000|for+i+in+0..n-1:
++if+a[i]+==+v2:
++++return+true
return+false|2822001|为了使这更具体一点，假设你的钥匙是名字，你的价值观是居住的城市。现在比较一下“鲍勃琼斯在哈希表中吗？”“在散列表里有纽约人吗？”我们可以散列"Bob“，并查看相应的数组位置中是否有任何内容(因为"Bob”就是这样插入的)，但是我们没有类似的快速查找"New+York“的方法。|2822002|我假设这就是你要问的，你把术语搞混了。如果这不是你想要的，请评论。|2822003|entityMap^0|0|I|1|K|1|12|1|1H|1|1O|1|1S|1|1Z|1|0|6|1|F|3|0|N|8|0|0|C|2|1B|8|1V|F|0|A|2|K|2|1C|2|0|0|0|0^^$0|@$1|2|3|4|5|6|7|12|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|13|8|@$D|14|E|15|F|G]|$D|16|E|17|F|G]|$D|18|E|19|F|G]|$D|1A|E|1B|F|G]|$D|1C|E|1D|F|G]|$D|1E|E|1F|F|G]|$D|1G|E|1H|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|1I|8|@$D|1J|E|1K|F|G]|$D|1L|E|1M|F|G]]|9|@]|A|$]]|$1|J|3|K|5|6|7|1N|8|@$D|1O|E|1P|F|G]]|9|@]|A|$]]|$1|L|3|M|5|N|7|1Q|8|@]|9|@]|A|$O|P]]|$1|Q|3|R|5|6|7|1R|8|@$D|1S|E|1T|F|G]|$D|1U|E|1V|F|G]|$D|1W|E|1X|F|G]]|9|@]|A|$]]|$1|S|3|T|5|6|7|1Y|8|@$D|1Z|E|20|F|G]|$D|21|E|22|F|G]|$D|23|E|24|F|G]]|9|@]|A|$]]|$1|U|3|V|5|N|7|25|8|@]|9|@]|A|$O|P]]|$1|W|3|X|5|6|7|26|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|27|8|@]|9|@]|A|$]]|$1|10|3|-4|5|6|7|28|8|@]|9|@]|A|$]]]|11|$]]

I think you are confusing terminology and also complicating matters by thinking about buckets.

Let's imagine a hash table that is implemented in as an array <code>a</code> of length <code>n</code>. Let's also imagine we have <code>n</code> possible keys and a perfect hash function <code>H</code> that maps each key <code>k</code> to a unique index <code>i</code> in <code>a</code>.

Let's initialize our hash table by setting every value in <code>a</code> to <code>nil</code>.

We can insert a key, value pair <code>(k1, v1)</code> into our hash table by placing the value at the appropriate position in the array:

<pre><code>a[H(k1)] = v1
</code></pre>

Now let's say that later we forgot if <code>k1</code> is in the hash table and we want to check if it's there. To do this we simply look up <code>a[H(k1)]</code> and see if any value is there, i.e. <code>a[H(k1)] != nil</code>. This is clearly a constant time lookup.

But what if we want to see if <code>v1</code>, or even some other <code>v2</code> is anywhere in our hashtable? This is not so easy because we have no function that maps a <code>vi</code> to a position in our array. It could be associated with any key. So the only way to see if it exists in the table is to scan the entire array, checking every value:

<pre><code>for i in 0..n-1:
 if a[i] == v2:
 return true
return false
</code></pre>

To make this a bit more concrete, imagine your keys are names, and your values are cities of residence. Now compare asking "Is Bob Jones in the hash table?" to "Is there anyone from New York in the hash table?". We can hash "Bob Jones" and see if there's anything in the corresponding array position (because that's how "Bob Jones" would have been inserted), but we have no similarly quick way to look up "New York".

I am assuming this is what you are asking, and you have confused the terminology a bit. Please comment if this is not what you wanted.

blocks|key|1406924|text|听起来你在寻找更详细的解释！|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1406925|假设您已经了解到数组元素查找需要O(1)，也就是说，如果我已经知道我想在数组中查找第100个元素，那么它只需要O(1)，因为这是一个简单的内存地址查找(通过将100添加到第一个元素的地址)。|1406926|散列方法利用这种内存地址查找来实现O(1)平均时间。显然，这意味着您需要能够将查找键转换为内存地址。让我给出一个非常简单的例子，说明这是如何在哈希表中工作的(为了清楚起见，字典在引擎盖下实现了hashtable，所以当我提到hashtable时，同样的原则也适用于字典)。|1406927|简化的示例场景；我们需要根据客户的名字查找他们的邮件地址。为了简单起见，假设名称是唯一的，并且它们有普通的a到z字母。假设我们最初只为10个客户设计(即他们的名字和地址)。|1406928|现在让我们说，我们必须通过在哈希表中存储名称-地址对来解决这个问题，并且我们必须创建我们自己的散列函数！一个哈希函数，它以名称作为参数并将其转换为内存查找！|1406929|现在花点时间想想这里需要多少个数组？他们的类型是什么，他们的大小是什么？|1406930|我们肯定需要一个数组来存储邮件地址。尺寸应该是多少？嗯，我们需要存储10个邮件地址，所以大小必须是10！我们还需要第二个数组来存储第一个数组的元素索引！！换句话说，我们需要第二个数组来为我们的客户名称存储对邮件地址(来自第一个数组)的引用。这个数组的大小应该是多少？绝对大于10！但这真的取决于我们设计的哈希函数。为了简单起见，让我们创建一个散列函数，它只接受name参数的第一个字母，并将其转换为索引。也就是说，如果名称从A开始，那么它的哈希值是1，b是2，c是3.Z是26。因此，至少我们的查找数组大小必须为26+(您一定认为这是存储10个地址的大量空间的浪费！！但这可能是值得的，因为它将给我们提供性能)，让我们试着用一个例子来理解这一点。假设我们的第一个顾客名叫鲍勃。要存储Bob的地址，第一步是在邮件地址数组中找到第一个空元素。这是名字，所以整个邮件地址数组都是空的。我们可以将Bob的地址存储在索引0的邮件地址数组中。当我们存储这个地址时，我们也会在索引0处将它标记为Bob的地址。(我使用这个“标记”术语来解释查找和搜索)，然后我们找出名字Bob的哈希值。在这种情况下，应该是2！因此，在位置2的查找数组中，我们存储0。(即Bob的邮件地址索引)。现在假设我们的第二个客户是Hamish；我们将Hamish的邮件地址存储在邮件地址数组中的索引1(即第二个元素)；将其标记为Hamish的地址，然后查找Hamish的哈希值。由于Hamish从‘H’开始，值将为8。因此，在位置8的查找数组中，我们存储值1(即Hamish地址的索引)。我们可以对所有10个客户重复这一过程，并存储他们的地址。现在，当您想要查找Bob的地址时，只需遵循一个简单的两步过程，就可以非常快地查找它。步骤1-将名称Bob转换为哈希值；回答为2；继续检查邮件地址数组中的位置2；如果它被标记为Bob的地址，则返回位置2+!！对Hamish也是如此；H->给出8。继续从位置8查找地址；如果它被标记为Hamish的地址，则从位置8返回地址。这种机制称为“查找”。如果您没有创建第二个数组(查找数组)，那么您将只有邮件地址数组，您必须逐个查看每个地址，并检查它是否标记了您要查找的客户名称！现在，如果有两个客户的名字以同一个字母开头呢？这叫做哈希冲突，可以用不同的方法来处理。如果我们需要存储10000个名字呢？这意味着我们必须使用一个更好的散列函数，这样就可以减少哈希冲突。我在这里不涉及这两个术语，因为我认为这个问题只需要解释查找和搜索。|1406931|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|S|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|T|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|U|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|V|8|@]|9|@]|A|$]]|$1|N|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|O|$]]

Sounds like you are in search of more elaborated explanation!

I assume that you already understand that array element lookup takes O(1) i.e. if I already knew that I wanted to lookup 100th element in array then it would only take me O(1) because this is a simple memory address lookup (by adding 100 to the first element's address). 

The method of hashing makes use of this memory address lookup to achieve O(1) average time. Now obviously this means that you need to be able to convert lookup key to memory address. Let me give you a very simplified example of how this works in a hashtable (just to be clear, dictionaries implement hashtable under the hood so when I mention hashtable , the exact same principles are applicable to dictionaries too).

The simplified example scenario; we need to lookup mailing addresses of customers by their first name. For simplicity assume that names are going to be unique and they've normal a to z letter. Let's say initially we are designing this for only 10 customers (i.e. their names and their addresses). 

Now lets say that we must solve this by storing name-addresses pairs in hashtable and we must create our own hashfunction!!! A hashfunction which would take name as a parameter and convert it into a memory lookup!!. 

Now take a moment and think how many arrays are required here? What would be their type and what would be their size? 
We definitely need one array to store mailing addresses. What should be the size? Well we need to store 10 mailing addresses so size has to be 10! 
We would also need second array for storing element indexes of first array!! Or in other words we need a second array to store references to mailing addresses (from first array) for our customer names. What should be the size of this array? Definitely larger than 10! But it really comes down to the hashfunction we design. For simplicity let's create a hashfunction which simply takes first letter of the name parameter and converts it to index. i.e. If name starts from A then it hashvalue is 1, for b it is 2, for c it is 3... for z it is 26. So at the least our lookup array size has to be 26 (you must be thinking that that's the wastage of lot of space for storing 10 addresses!! but it may worth it since it is going to give us performance)
Let’s try to understand this with an example. Let’s say our first customer name is Bob. To store address for Bob first step is to find the first empty element in mailing address array. This is the first name so whole mailing address array is empty. We can store Bob’s address at index zero in mailing address array. When we store this address we’ll also mark it as Bob’s address at index 0. (I’m using this ‘marking’ terminology to later explain lookup vs searching) Then we find out hashvalue for name Bob. In this case it would be 2! So in the lookup array at location 2 we store 0. (i.e. the index to mailing address for Bob). Now lets say our second customer is Hamish; we store mailing address for Hamish at index 1 (i.e. the second element) in mailing address array; mark it as Hamish’s address and then we find out hashvalue for Hamish. Since Hamish starts from ‘H’, value would be 8. So in our lookup array at location 8 we store value 1 (i.e. the index for Hamish’s address). We can repeat this procedure for all 10 customers and store their addresses. Now later when you want to lookup Bob’s address you could look it up very fast simply by following a simple two step procedure. Step 1- convert name Bob to hashvalue ; answer is 2; go ahead and check location 2 in mailing address array; if it is marked as Bob’s address then return location 2 !! Same for Hamish; H-> gives 8. Go ahead and look up address from location 8; if it is marked as Hamish’s address then return address from location 8. This mechanism is called ‘looking up’. If you hadn’t created the second array (lookup array) then you’d only have mailing address array and you’d have to go through each address one by one and check if it is marked with the customer name you are looking for or not!. 
Now, what if there are two customer names starting with same letter? That’s called hash collision and that can be dealt with different approaches. What if we need to store 10000 names? That means we are have to use a better hashfunction which would give us less hash collisions. I’m not covering those two terminology here since I believe that question only demanded explaining lookup vs searching.

blocks|key|2822062|text|问得好！|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2822063|假设|2822064|我们要将strings映射到values。|ordered-list-item|offset|length|style|CODE|2822065|O(1)中的hashFunction(string)+=>+hashedIndex+:+int|2822066|valueArray+:+[any]存储value的|2822067|valueIndex+:+int是valueArray中的第一个空索引。|2822068|lookupArray+:+[int]将每个valueIndex存储在hashedIndex|2822069|数组查找是O(1)。|2822070|//+Setting+a+value

valueArray[valueIndex]+=+value+

hashedIndex+=+hashFunction(string)

lookupArray[hashedIndex]+=+valueIndex


//+Looking+up+a+value

hashedIndex+=+hashFunction(string)+//+O(1)

valueIndex+=+lookupArray[hashedIndex];+//+O(1)+array+lookup

value+=+valueArray[valueIndex];+//+O(1)+array+lookup|code-block|syntax|javascript|2822071|许多细节遗漏了清楚地回答你的问题。|2822072|希望这能帮上忙！|2822073|entityMap^0|0|0|4|6|E|5|0|6|15|0|0|I|K|5|0|0|G|H|A|0|0|J|M|A|Z|B|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|15|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|16|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|17|8|@$G|18|H|19|I|J]|$G|1A|H|1B|I|J]]|9|@]|A|$]]|$1|K|3|L|5|F|7|1C|8|@$G|1D|H|1E|I|J]]|9|@]|A|$]]|$1|M|3|N|5|F|7|1F|8|@$G|1G|H|1H|I|J]|$G|1I|H|1J|I|J]]|9|@]|A|$]]|$1|O|3|P|5|F|7|1K|8|@$G|1L|H|1M|I|J]|$G|1N|H|1O|I|J]]|9|@]|A|$]]|$1|Q|3|R|5|F|7|1P|8|@$G|1Q|H|1R|I|J]|$G|1S|H|1T|I|J]|$G|1U|H|1V|I|J]]|9|@]|A|$]]|$1|S|3|T|5|F|7|1W|8|@]|9|@]|A|$]]|$1|U|3|V|5|W|7|1X|8|@]|9|@]|A|$X|Y]]|$1|Z|3|10|5|6|7|1Y|8|@]|9|@]|A|$]]|$1|11|3|12|5|6|7|1Z|8|@]|9|@]|A|$]]|$1|13|3|-4|5|6|7|20|8|@]|9|@]|A|$]]]|14|$]]

Great question!

Assume 

<ol>
<li>We want to map <code>string</code>s to <code>value</code>s</li>
<li><code>hashFunction(string) =&gt; hashedIndex : int</code> in O(1) </li>
<li><code>valueArray : [any]</code> stores <code>value</code>s</li>
<li><code>valueIndex : int</code> is the first empty index in <code>valueArray</code></li>
<li><code>lookupArray : [int]</code> stores each <code>valueIndex</code> at <code>hashedIndex</code></li>
<li>array lookups are O(1).</li>
</ol>

<pre class="lang-js prettyprint-override"><code>// Setting a value

valueArray[valueIndex] = value 

hashedIndex = hashFunction(string)

lookupArray[hashedIndex] = valueIndex


// Looking up a value

hashedIndex = hashFunction(string) // O(1)

valueIndex = lookupArray[hashedIndex]; // O(1) array lookup

value = valueArray[valueIndex]; // O(1) array lookup
</code></pre>

Lots of details omitted to answer your question clearly. 

Hope that helps!

blocks|key|1407025|text|我想“哈希”这个词是在吓唬人。在场景后面，哈希表是将键/值对存储在数组中的数据结构。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1407026|这里唯一的区别是，我们不关心键值对的位置。这里没有索引。查找数组项O(1)。它与阵列大小无关，与位置无关。您只需输入索引号，并检索项。|1407027|所以查了多少时间才能完成。它是O(1)。|1407028|在哈希表中，当存储键/值对时，键值将被散列并存储在相应的内存槽中。|1407029|{name:"bob"}+//name+will+be+hashed

hash(name)+=+ab1234wq+//this+is+the+memory+address
[["name","bob"]]+//+will+be+store+at+memory+adress+ab1234wq|code-block|syntax|javascript|1407030|当您查找"name“时，它将被散列，并且作为散列函数的主要特性，它将返回与"ab1234wq”相同的结果。因此，编程引擎将查看这个地址，将看到数组并返回值。如您所见，此操作与数组查找相同。|1407031|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|S|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|T|8|@]|9|@]|A|$]]|$1|H|3|I|5|J|7|U|8|@]|9|@]|A|$K|L]]|$1|M|3|N|5|6|7|V|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

i think the word &quot;hash&quot; is scaring people. Behind the scene, hash tables are data structures that stores the key/value pairs in an array.
The only difference here is, we do not care about the position of the key value pair. There is no INDEX here. Look up for an array item O(1). it is independent of size of the array and independent of position. you just enter index number, and item is retrieved.
so how much time did look up need to complete. it is O(1).
In hash tables, when you store key/value pair, key value gets hashed and stored in the corresponding memory slot.
<pre><code>{name:&quot;bob&quot;} //name will be hashed

hash(name) = ab1234wq //this is the memory address
[[&quot;name&quot;,&quot;bob&quot;]] // will be store at memory adress ab1234wq
</code></pre>
when you look up for &quot;name&quot;, it will get hashed and as the main feature of hashing functions, it will return same the result &quot;ab1234wq&quot;. So the programming engine will look at this address, will see the array and will return the value. As you can see, this operation is same as array look up.

Technically speaking, based on posts I've read here, Hash table is indeed O(n) time lookup in the worst case. But I don't get how the internal mechanics guarantee it to be O(1) time on average.

My understanding is that given some n elements, the ideal case is there are n buckets, which result in O(1) space. This is where I'm stuck. Suppose I want to lookup whether a key is in the dictionary, this definitely takes me O(n) time. So why does it make a difference when I want to search whether an element is in the hash table by using its key's hash value? To put it concisely, searching using raw key values gives O(n) time but using hash values it's O(1) time. Why is that? 

Wouldn't I still need to look up the hash values one by one to see which one matches? Why does the hashing let me know immediately which element to retrieve or whether such an element exists or not?

Why is a hash table lookup only O(1) time when searching for a key is O(n)?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

从技术上讲，根据我在这里读过的文章，在最坏的情况下，哈希表确实是O(n)时间查找。但我不知道内部力学如何保证它平均是O(1)时间。我的理解是，给定一些n个元素，理想的情况是有n个桶，这就产生了O(1)空间。这就是我被困的地方。假设我想查找字典中是否有一个键，这肯定要花我O(n)时间。那么，当我想通过使用元素的键的散列值...

问为什么哈希表在搜索密钥时只查找O(1)时间是O(n)？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么哈希表在搜索密钥时只查找O(1)时间是O(n)？EN