路的尽头在哪

Hash 一般称为散列，音译是“哈希”，以下就成之为哈希，毕竟感觉高大上。

摘自百度百科的哈希的作用：

是把任意长度的输入（又叫做预映射pre-image）通过哈希算法变换成固定长度的输出，该输出就是哈希值。

这种转换是一种压缩映射，也就是，哈希值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。

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

所有哈希函数都有下面的特性：

两个不同的输入值，根据同一哈希函数计算出哈希值相同的现象叫做碰撞。

一般的哈希算法都应该具有下面2个能力：

抗碰撞能力：对于任意两个不同的数据块，其hash值相同的可能性极小；对于一个给定的数据块，找到和它hash值相同的数据块极为困难。

抗篡改能力：对于一个数据块，哪怕只改动其一个比特位，其hash值的改动也会非常大。

算法名	算法简介
直接定址法	直接以关键字k或者k加上某个常数（k+c）作为哈希地址。
数字分析法	提取关键字中取值比较均匀的数字作为哈希地址。
除留余数法	用关键字k除以某个不大于哈希表长度m的数p，将所得余数作为哈希表地址。
分段叠加法	按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。
平方取中法	如果关键字各个部分分布都不均匀的话，可以先求出它的平方值然后按照需求取中间的几位作为哈希地址。
伪随机数法	采用一个伪随机数当作哈希函数。

衡量一个哈希函数的好坏的重要指标就是发生碰撞的概率以及发生碰撞的解决方案。

任何哈希函数基本都无法彻底避免碰撞，常见的解决碰撞的方法有以下几种：

方法名	方法介绍
开放定址法	开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址；只要散列表足够大，空的散列地址总能找到，并将记录存入。
链地址法	将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。
再哈希法	当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止。
建立公共溢出区	将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中。

最后看下 HashMap 的内部结构图，具体分析在以后在 HashMap源码阅读里写。

WhatisHash