hash函数学习总结，以及与hashcode()、hashMap的关系

以前一直觉得hash函数很深奥，上王珊的《数据库实现原理》的时候，似乎明白了一点点，但是到学java
的时候，频繁接触到hashcode()，hashMap这些，就总在想这三者之间有关系吗？hash函数是什么？hashcode()，
hashMap和hash函数又有什么关系呢？

今天终于对这个问题有了初步的学习和理解：

1.什么是hash函数：
1）来自：http://beyond911.bokee.com/1047973.html

什么是HASH函数(经典例子)                                  

让我们先来了解一些基本知识，作作预热只有这样才能更好的了解hash。

Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。

简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

HASH主要用于信息安全领域中加密算法，他把一些不同长度的信息转化成杂乱的128位的编码里,叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系

2）来自：http://www.hour41.com/blog/hour41/entry/200701255
计算理论中，没有Hash函数的说法，只有单向函数的说法。所谓的单向函数，是一个复杂的定义，大家可以去看计算理论或者密码学方面的数据。用“人类”的语言描述单向函数就是：如果某个函数在给定输入的时候，很容易计算出其结果来；而当给定结果的时候，很难计算出输入来，这就是单项函数。各种加密函数都可以被认为是单向函数的逼近。Hash函数（或者成为散列函数）也可以看成是单向函数的一个逼近。即它接近于满足单向函数的定义。

Hash函数还有另外的含义。实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间，使得数据容易保存。除此以外，Hash函数往往应用于查找上。所以，在考虑使用Hash函数之前，需要明白它的几个限制：

1. Hash的主要原理就是把大范围映射到小范围；所以，你输入的实际值的个数必须和小范围相当或者比它更小。不然冲突就会很多。
2. 由于Hash逼近单向函数；所以，你可以用它来对数据进行加密。
3. 不同的应用对Hash函数有着不同的要求；比如，用于加密的Hash函数主要考虑它和单项函数的差距，而用于查找的Hash函数主要考虑它映射到小范围的冲突率。

3）自己的总结：
   a）hash函数就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。
例如，散列算法为求余的hash函数。
   b）实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间，使得数据容易保存。
   c）在数据结构中，hash就是找到一种数据内容和数据存放地址之间的映射关系，比如，31对10求余后得1，就把31存放到第一个桶里（或者是第一块内存单元中），即把数据和存放地址建立映射关系；
   d）所以，有了数据内容和数据存放地址之间的映射关系，Hash函数往往应用于查找上。不过，利用hash函数的查找跟以前自己理解的不同，以前自己以为是通过hash函数就能立即找到存储地址，就像HashMap中根据key立即能找到value一样，其实不是这样的，hash函数只不过是根据散列算法和解决冲突的方法来提供一种定位和查找的方式，hashmap中根据可以马上找到value值是理所当然的，但是根据hash函数找到key值就不是立即的了。当然，为了方便查找，尽量使得hash函数无冲突，可以唯一确定地址是最理想的。娃哈哈，终于弄清楚这一点了！
   e）Hash函数是指把一个大范围映射到一个小范围，所以hash函数是求余之类的压缩函数，（比如，11，13的范围压缩为1，3），而不是10x＋7这样的扩散函数，（比如，11，13的范围扩散为117，137）；
   f）由于Hash逼近单向函数；所以，你可以用它来对数据进行加密。
   g）不同的应用对Hash函数有着不同的要求；比如，用于加密的Hash函数主要考虑它和单项函数的差距，而用于查找的Hash函数主要考虑它映射到小范围的冲突率。

2.散列表相关知识的系统学习：
数据结构自考网：http://student.zjzk.cn/course_ware/data_structure/web/chazhao/chazhao9.4.1.htm

3.  JDK中HashMap的分析
1）来自：http://chinakite.iteye.com/blog/25073
2）请问hashtable类里面的hash函数是怎么样的？
来自：http://topic.csdn.net/t/20020311/09/567386.html

他是调用每个类自己本身的hashCode的方法来确定的 
  public   synchronized   Object   put(Object   key,   Object   value)   { 
  ... 
  int   hash   =   key.hashCode();//就是这里了 
  int   index   =   (hash   &   0x7FFFFFFF)   %   tab.length; 
  ... 
          } 
  详细请看java的源文件


String的散列值是由内容转换来的，Object类的却省散列函数返回对象地址转换来的散列值。

4.面试题：
来自：http://www.javaref.cn/topics/Question/10566.html

问题：

a)请问哈希表 (hashtable) 是如何存储数据的 ？

答案： Hashtable 是用来存储 key 和 value 对的数据结构 , 根据设定的 hash 函数 H(key) 和处理冲突的方法将一组关键字（ key ）映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中存储位置，这种表便成为 hashtable.

b)是否两个键值通过 hash 函数产生的映射地址会一样？怎么办？

答案 : 是，一般情况下，完全避免冲突是很难的。因为通常关键字集合会比目标地址空间大。哈希函数要尽量避免冲突（避免不同的关键字产生相同的 hash 值），使一组关键字的哈西地址尽可能的均匀分布在整个地址区间。所以有一些冲突处理方法：开放定址法，再哈希法，链地址法（用链表保存冲突的值），公共溢出区。 

关于哈希表，有个与实际编程更密切的问题可以一问：为保证逻辑上的正确性，哈希表对可以作为键值的类型有什么要求？  C++：除容器对元素类型的标准需求外，还需overload == 和 < Java：需override equals(逻辑上的正确性)和hashCode(性能) C#：需override Equals(逻辑上的正确性)和HashCode(性能)