A--->function()---> B

源数据A经过function()的运算得到B.这里的function()就是哈希函数，它是某一种hash算法的实现。得到的数据B就是hashCode,它是源数据A的哈希体现。

如果我们将A->B这样的的关系保存下来，存储这个对应关系的我们称为哈希表。

补充：

还是正经的说下。

什么是hash算法：

将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是hash算法，而通过原始数据映射之后得到的值就是哈希（hash）值。

哈希表法数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法。

哈希算法若对于关键字集合中的任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数是均匀的（Uniform）哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。

 哈希表（散列表），是基于关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数（哈希函数），存放记录的数组叫做散列表。

  上面所提到的哈希函数是指：有一个对应关系 f ，使得每个关键字和结构中一个唯一的存储位置相对应，这样在查找时，我们不需要像传统的查找算法那样进行比较，而是根据这个对应关系 f 找到给定值K的像f（K）。

   哈希算法
  构造哈希函数的方法有很多。首先需要明确什么是“好” 的哈希算法。若对于关键字集合中的任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数是均匀的（Uniform）哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。

一个hash函数需要满足

1. 接受一个单一的参数，这个参数可以是任何类型，但是只能是一个。

2. 返回一个整型值(一般情况下)。

3. 输出的哈希地址均匀分布在整个地址区间中。

4. 对于两个相同的输入，输出必须相同。

5. 对于两个不同的输入，输出相同的概率需要做到非常小。

6. hash的计算不能过于复杂，时间复杂度尽可能地低。

哈希表(也称为哈希图)是一种将键映射到值的数据结构。 它是一种称为散列的技术，另一部分是散列函数。 哈希函数是一种算法，它生成一个索引，该索引可在哈希表中找到或存储值。

Some important notes about hash tables:

有关哈希表的一些重要说明：

1. Values are not stored in a sorted order.

   
   

   值未按排序顺序存储。

2. You mush account for potential collisions. This is usually done with a technique called chaining. Chaining means to create a linked list of values, the keys of which map to a certain index.

   
   

   您必须考虑潜在的碰撞。 通常使用称为链接的技术来完成此操作。 链接意味着创建值的链接列表，其键映射到某个索引。

哈希表的实现 (Implementation of a hash table)

The basic idea behind hashing is to distribute key/value pairs across an array of placeholders or "buckets" in the hash table.

散列背后的基本思想是在散列表中的一组占位符或“存储桶”之间分布键/值对。

A hash table is typically an array of linked lists. When you want to insert a key/value pair, you first need to use the hash function to map the key to an index in the hash table. Given a key, the hash function can suggest an index where the value can be found or stored:

哈希表通常是链接列表的数组。 当您要插入键/值对时，首先需要使用哈希函数将键映射到哈希表中的索引。 给定一个键，哈希函数可以建议一个索引，可以在其中找到或存储该值：

index = f(key, array_size)

This is often done in two steps:

这通常分两个步骤完成：

hash = hashfunc(key)index = hash % array_size

Using this method, hash is independent of the size of the hash table. hash is reduced to an index – a number between 0, the start of the array, and array_size - 1, the end of the array – using the modulo (%) operator.

使用此方法， hash与哈希表的大小无关。 使用模(％)运算符将hash减少为一个索引-一个介于0(在数组的开头)和array_size - 1 (在数组的结尾)之间的数字。

Consider the following string, S:

考虑以下字符串S ：

string S = “ababcd”

You need to count the frequency of all the characters in S. The easiest way to do this is to iterate through all the possible characters and count the frequency of each, one by one.

您需要计算S中所有字符的频率。 最简单的方法是遍历所有可能的字符并逐个计数每个字符的频率。

This works, but it's slow – the time complexity of such an approach is O(26*N), with N being the size of the string S multiplied by 26 possible characters from A-Z.

这可行，但是很慢–这种方法的时间复杂度为O(26 * N)，其中N是字符串S大小乘以AZ中的26个可能的字符。

void countFre(string S){for(char c = ‘a’;c <= ‘z’;++c){int frequency = 0;for(int i = 0;i < S.length();++i)if(S[i] == c)frequency++;cout << c << ‘ ‘ << frequency << endl;}}

Output:

输出：

a 2b 2c 1d 1e 0f 0…z 0

Let's take a look at a solution that uses hashing.

让我们看一下使用哈希的解决方案。

Take an array and use the hash function to hash the 26 possible characters with indices of the array. Then iterate over S and increase the value of the current character of the string with the corresponding index for each character.

取得一个数组，并使用哈希函数对带有数组索引的26个可能的字符进行哈希处理。 然后遍历S并使用每个字符的相应索引增加字符串的当前字符的值。

The complexity of this hashing approach is O(N), where N is the size of the string.

这种哈希方法的复杂度为O(N)，其中N是字符串的大小。

int Frequency[26];int hashFunc(char c){return (c - ‘a’);}void countFre(string S){for(int i = 0;i < S.length();++i){int index = hashFunc(S[i]);Frequency[index]++;}for(int i = 0;i < 26;++i)cout << (char)(i+’a’) << ‘ ‘ << Frequency[i] << endl;}

Output

输出量

a 2b 2c 1d 1e 0f 0…z 0

哈希冲突 (Hash Collisions)

Since your hash map will probably be significantly smaller than the amount of data you're processing, hash collisions are unavoidable. There are two main approaches to handling collisions: chaining and open addressing.

由于您的哈希映射可能会大大小于您正在处理的数据量，因此哈希冲突不可避免。 处理冲突有两种主要方法： 链接和开放式寻址 。

链式 (Chaining)

As mentioned earlier, chaining means that each key/value pair in the hash table, the value is a linked list of data rather than a single cell.

如前所述，链接意味着哈希表中的每个键/值对，值都是数据的链表，而不是单个单元格。

For example, imagine that the key 152 holds the value "John Smith". If the value "Sandra Dee" is added to the same key, "Sandra Dee" is added as another element to key 152, just after "John Smith".

例如，假设键152的值是“ John Smith”。 如果将值“ Sandra Dee”添加到同一键，则在“ John Smith”之后，将“ Sandra Dee”作为另一个元素添加到键152。

152: [["John Smith", "p01"]]...152: [["John Smith", "p01"] ["Sandra Dee", "p02"]]

The main drawback of chaining is the increase in time complexity. Instead of 0(1) as with a regular hash table, each lookup will take more time since we need to traverse each linked list to find the correct value.

链接的主要缺点是时间复杂度的增加。 代替常规哈希表的0(1)，每次查找将花费更多时间，因为我们需要遍历每个链表以找到正确的值。

开放式寻址 (Open addressing)

Open addressing means that, once a value is mapped to a key that's already occupied, you move along the keys of the hash table until you find one that's empty. For example, if "John Smith" was mapped to 152, "Sandra Dee" will be mapped to the next open index:

开放式寻址意味着，将值映射到已被占用的键之后，您将沿着哈希表的键移动，直到找到一个空的键。 例如，如果“ John Smith”映射到152，则“ Sandra Dee”将映射到下一个打开的索引：

152: ["John Smith", "p01"]...152: ["John Smith", "p01"],153: ["Sandra Dee", "p02"]

The main drawback to open addressing is that, when you look up values, they might not be at the key map you expect them at. Instead, you have to traverse different parts of the hash table to find the value you're looking for.

开放式寻址的主要缺点是，当您查找值时，它们可能不在您期望的键映射中。 相反，您必须遍历哈希表的不同部分以查找所需的值。

哈希表概念
哈希表（散列表），是基于关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数（哈希函数），存放记录的数组叫做散列表。

上面所提到的哈希函数是指：有一个对应关系 f ，使得每个关键字和结构中一个唯一的存储位置相对应，这样在查找时，我们不需要像传统的查找算法那样进行比较，而是根据这个对应关系 f 找到给定值K的像f（K）。

哈希算法
构造哈希函数的方法有很多。首先需要明确什么是“好” 的哈希算法。若对于关键字集合中的任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数是均匀的（Uniform）哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。

总结：

优点：

不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即0(1）的时间级。实际上，这只需要几条机器指令。

哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。

如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

缺点：

它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。

1、哈希表(也称为哈希图)是一种将键映射到值的数据结构。

  它是一种称为散列的技术，另一部分是散列函数。 哈希函数是一种算法，它生成一个索引，该索引可在哈希表中找到或存储值。

  有关哈希表的一些重要说明：

  值未按排序顺序存储。

  您必须考虑潜在的碰撞。 通常使用称为链接的技术来完成此操作。 链接意味着创建值的链接列表，其键映射到个索引。

  散列背后的基本思想是在散列表中的一组占位符或“存储桶”之间分布键/值对。

2、哈希算法的定义和原理：

  将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则，就是哈希算法。而通过原始数据映射之后得到的二进制值串就是哈希值。

  设计一个优秀的哈希算法，需要满足下面几点要求：

  a.从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）

  b.对输入的数据比较敏感，原始数据即使修改一个字节，最后得到的哈希值也大不相同

  c.散列冲突的概率要小，对于不同的原始数据，哈希值相同的概率非常小

  d.哈希算法的执行效率要尽量高，针对较长的文本，也能快速地计算出哈希值

  哈希算法的应用非常多，选择常见的七个进行说明。分别是：

  安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。

哈希算法并不是一个特定的算法而是一类算法的统称。哈希算法也叫散列算法,一般来说满足这样的关系:f(data)=key,输入任意长度的data数据,经过哈希算法处理后输出一个定长的数据key。同时这个过程是不可逆的,无法由key逆推出data。如果是一个data数据集,经过哈希算法处理后得到key的数据集,然后将keys与原始数据进行一一映射就得到了一个哈希表。一般来说哈希表M符合M[key]=data这种形式。哈希表的好处是当原始数据较大时,我们可以用哈希算法处理得到定长的哈希值key,那么这个key相对原始数据要小得多。我们就可以用这个较小的数据集来做索引,达到快速查找的目的。稍微想一下就可以发现,既然输入数据不定长,而输出的哈希值却是固定长度的,这意味着哈希值是一个有限集合,而输入数据则可以是无穷多个。那么建立一对一关系明显是不现实的。所以"碰撞"(不同的输入数据对应了相同的哈希值)是必然会发生的,所以一个成熟的哈希算法会有较好的抗冲突性。同时在实现哈希表的结构时也要考虑到哈希冲突的问题。密码上常用的MD5,SHA都是哈希算法,因为key的长度(相对大家的密码来说)较大所以碰撞空间较大,有比较好的抗碰撞性,所以常常用作密码校验。

   哈希算法
  构造哈希函数的方法有很多。首先需要明确什么是“好” 的哈希算法。若对于关键字集合中的任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数是均匀的（Uniform）哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。

一个hash函数需要满足

接受一个单一的参数，这个参数可以是任何类型，但是只能是一个。

返回一个整型值(一般情况下)。

输出的哈希地址均匀分布在整个地址区间中。

对于两个相同的输入，输出必须相同。

对于两个不同的输入，输出相同的概率需要做到非常小。