什么是编程中的哈希映射以及在哪里可以使用它 [英] 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 函数，它将这个索引分配给每个项目.当你在寻找一个项目时，你应该能够提前计算出指数.就像在真正的字典中一样，您会看到单词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屋！