HashMap">HashMap

光从名字上应该也能猜到，HashMap必定是基于hash算法实现的，这种基于hash实现的map叫做散列表（hash table）。

散列表中维护了一个数组，数组的每一个元素被称为一个桶（bucket），当你传入一个key = "a"举办查询时，散列表会先把key传入散列（hash）函数中举办寻址，获得的功效就是数组的下标，然后再通过这个下标会见数组即可获得相关联的值。

苏州软件定制开拓 较容易领略" class="aligncenter size-full wp-image-29725" title="63503acbly1fpu3a5d3p7j20j00bpwex" src="/uploads/allimg/c180909/153643F051C10-13964.jpg" />

我们都知道数组中数据的组织方法是线性的，它会直接分派一串持续的内存地点序列，要找到一个元素只需要按照下标来计较地点的偏移量即可（查找一个元素的起始地点为：数组的起始地点加上下标乘以该元素范例占用的地点巨细）。因此散列表在抱负的环境下，各类操纵的时间巨大度只有O(1)，这甚至高出了二叉查找树，固然抱负的环境并不老是满意的，关于这点之后我们还会提及。

为什么是hash？

hash算法是一种可以从任何数据中提取出其“指纹”的数据摘要算法，它将任意巨细的数据（输入）映射到一个牢靠巨细的序列（输出）上，这个序列被称为hash code、数据摘要可能指纹。较量着名的hash算法有MD5、SHA。

苏州软件定制开拓 较容易领略" class="aligncenter size-full wp-image-29726" title="Hash_function" src="/uploads/allimg/c180909/153643F0522360-25A8.png" />

hash是具有独一性且不行逆的，独一性指的是沟通的输入发生的hash code永远是一样的，而不行逆也较量容易领略，数据摘要算法并不是压缩算法，它只是生成了一个该数据的摘要，没有将数据举办压缩。压缩算法一般都是利用一种更节减空间的编码法则将数据从头编码，解压缩只需要按着编码法则解码就是了，试想一下，一个几百MB甚至几GB的数据生成的hash code都只是一个拥有牢靠长度的序列，假如再能逆向解压缩，那么其他压缩算法该情何故堪？

我们上述接头的仅仅是在暗码学中的hash算法，而在散列表中所需要的散列函数是要可以或许将key寻址到buckets中的一个位置，散列函数的实现影响到整个散列表的机能。

一个完美的散列函数要可以或许做到匀称地将key漫衍到buckets中，每一个key分派到一个bucket，但这是不行能的。固然hash算法具有独一性，但同时它还具有反复性，独一性担保了沟通输入的输出是一致的，却没有担保差异输入的输出是纷歧致的，也就是说，完全有大概两个差异的key被分派到了同一个bucket（因为它们的hash code大概是沟通的），这叫做碰撞斗嘴。总之，抱负很饱满，现实很骨感，散列函数只能尽大概地淘汰斗嘴，没有步伐完全消除斗嘴。

散列函数的实现要领很是多，一个优秀的散列函数要看它能不能将key漫衍匀称。首先先容一种最简朴的要领：除留余数法，先对key举办hash获得它的hash code，然后再用该hash code对buckets数组的元素数量取余，获得的功效就是bucket的下标，这种要领简朴高效，也可以当做对集群举办负载平衡的路由算法。

private int hash(Key key) {
   // & 0x7fffffff 是为了屏蔽标记位，M为bucket数组的长度
   return (key.hashCode() & 0x7fffffff) % M;
}

要留意一点，只有整数才气举办取余运算，昆山软件开发，假如hash code是一个字符串或此外范例，昆山软件开发，那么你需要将它转换为整数才气利用除留余数法，不外Java在Object工具中提供了hashCode()函数，该函数返回了一个int值，所以任何你想要放入HashMap的自界说的抽象数据范例，都必需实现该函数和equals()函数，这两个函数之间也遵守着一种约定：假如a.equals(b) == true，那么a与b的hashCode()也必需是沟通的。

下面为String类的hashCode()函数，它先遍历了内部的字符数组，然后在每一次轮回中计较hash code（将hash code乘以一个素数并加上当前轮回项的字符）：

/** The value is used for character storage. */
private final char value[];
/** Cache the hash code for the string */
private int hash; // Default to 0
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

HashMap没有回收这么简朴的要领，有一个原因是HashMap中的buckets数组的长度永远为一个2的幂，而不是一个素数，假如长度为素数，那么大概会更适合简朴暴力的除留余数法（虽然除留余数法固然简朴却并不是那么高效的），顺便一提，时代的眼泪Hashtable就利用了除留余数法，它没有强制约束buckets数组的长度。