什么是编程中的哈希映射以及它可以在哪里使用 [英] What is a hash map in programming and where can it be used

问题描述

我经常听到人们谈论散列、散列映射和散列表.我想知道它们是什么以及你可以在哪里最好地使用它们.

I have often heard people talking about hashing and hash maps and hash tables. I wanted to know what they are and where you can best use them for.

推荐答案

首先你应该阅读这篇文章.

当您使用列表并且您正在寻找一个特殊项目时，您通常必须遍历整个列表.当您有大量列表时，这非常昂贵.
哈希表可以更快，在最好的情况下，您只需一次访问即可获得所需的项目.
它是如何工作的?就像字典一样……当您在字典中查找单词hashtable"时，您不是从a"下的第一个单词开始的.而是直接前进到字母h".然后到'ha'，'has'等等，直到你找到你的词.您正在使用字典中的索引来加快搜索速度.
哈希表的作用基本相同.每个项目都有一个唯一的索引(所谓的 hash).您使用此哈希进行查找.散列可以是普通链表中的索引.例如，您的哈希可能是一个像 2130 这样的数字，这意味着您应该查看列表中的位置 2130.在普通列表中查找已知索引非常简单快捷.
整个方法的问题是所谓的 hash function 将这个索引分配给每个项目.当您在寻找一个项目时，您应该能够提前计算索引.就像在真正的字典中一样，您会看到hashtable"这个词以字母h"开头，因此您知道大概的位置.
一个好的散列函数可以提供均匀分布在所有可能散列码空间上的散列码.当然，它会尽量避免collisions.当两个不同的项目获得相同的哈希码时，就会发生冲突.
例如，在 C# 中，每个对象都有一个 GetHashcode() 方法为其提供哈希(不一定是唯一的).这可用于在您的字典中查找和排序.

When you use lists and you are looking for a special item you normally have to iterate over the complete list. This is very expensive when you have large lists.
A hashtable can be a lot faster, under best circumstances you will get the item you are looking for with only one access.
How is it working? Like a dictionary ... when you are looking for the word "hashtable" in a dictionary, you are not starting with the first word under 'a'. But rather you go straight forward to the letter 'h'. Then to 'ha', 'has' and so on, until you found your word. You are using an index within your dictionary to speed up your search.
A hashtable does basically the same. Every item gets an unique index (the so called hash). You use this hash for lookups. The hash may be an index in a normal linked list. For instance your hash could be a number like 2130 which means that you should look at position 2130 in your list. A lookup at a known index within a normal list is very easy and fast.
The problem of the whole approach is the so called hash function which assigns this index to each item. When you are looking for an item you should be able to calculate the index in advance. Just like in a real dictionary, where you see that the word 'hashtable' starts with the letter 'h' and therefore you know the approximate position.
A good hash function provides hashcodes that are evenly distrubuted over the space of all possible hashcodes. And of course it tries to avoid collisions. A collision happens when two different items get the same hashcode.
In C# for instance every object has a GetHashcode() method which provides a hash for it (not necessarily unique). This can be used for lookups and sorting with in your dictionary.

当您开始使用哈希表时，您应该始终牢记正确处理冲突.在大型哈希表中很容易发生两个对象具有相同哈希的情况(可能您的 GetHashcode() 重载有问题，也可能发生了其他事情).

When you start using hashtables you should always keep in mind, that you handle collisions correctly. It can happen quite easily in large hashtables that two objects got the same hash (maybe your overload of GetHashcode() is faulty, maybe something else happened).

这篇关于什么是编程中的哈希映射以及它可以在哪里使用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！