哈希表就是 依據(jù)關(guān)鍵字可以根據(jù)一定的算法（哈希函數(shù)）映射到表中的特定位置 的思想建立的表斩跌。因此哈希表最大的特點(diǎn)就是可以根據(jù)f(K)函數(shù)得到其在數(shù)組中的索引。
java官方說(shuō)明中侨把，Object的：
- equals方法具有自反性、對(duì)稱性萍启、傳遞性女揭、一致性录肯，如果兩個(gè)對(duì)象執(zhí)行equals方法結(jié)果為true趴腋，則兩對(duì)象的哈希碼應(yīng)該是相等的。 如果重寫(xiě)equals方法嘁信，則一定要重寫(xiě)hashcode方法于样。
- hashcode方法是 返回對(duì)象的經(jīng)過(guò)處理后的內(nèi)存地址，由于每個(gè)對(duì)象的內(nèi)存地址都不一樣潘靖，所以哈希碼也不一樣穿剖。此方法為native方法，取決于JVM的內(nèi)部設(shè)計(jì)卦溢，一般是某種C地址的偏移糊余。
- 文檔中還給出了三條規(guī)定：
- 在對(duì)象沒(méi)有被修改的前提下，執(zhí)行多次調(diào)用单寂，該hashCode方法必須始終返回相同的整數(shù)贬芥。
- 如果兩個(gè)對(duì)象執(zhí)行equals方法結(jié)果為true，則分別調(diào)用hashCode方法產(chǎn)生的整數(shù)結(jié)果是相等的宣决。
- 非必要要求：兩個(gè)對(duì)象執(zhí)行equals方法結(jié)果為false蘸劈，則分別調(diào)用hashCode方法產(chǎn)生的整數(shù)結(jié)果是不相等的。
第三個(gè)要求雖然為非必需尊沸，但如果實(shí)現(xiàn)威沫，則可以提高散列表的性能贤惯。
Object的hash方法
Object類的hashCode. 返回對(duì)象的經(jīng)過(guò)處理后的內(nèi)存地址，由于每個(gè)對(duì)象的內(nèi)存地址都不一樣棒掠，所以哈希碼也不一樣孵构。這個(gè)是native方法，取決于JVM的內(nèi)部設(shè)計(jì)烟很，一般是某種C地址的偏移颈墅。
String的equals和hashCode方法
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;
}
該函數(shù)很簡(jiǎn)單，以31為權(quán)雾袱，每一位為字符的ASCII值進(jìn)行運(yùn)算恤筛，用自然溢出來(lái)等效取模，達(dá)到了目的——只要字符串的內(nèi)容相同谜酒，返回的哈希碼也相同叹俏。
- 選31作為乘子, 它可以被JVM優(yōu)化：31 * i = (i << 5) - i，并且是一個(gè)奇質(zhì)數(shù)
- unicode編碼（萬(wàn)國(guó)碼,原有的Ascii編碼從單字節(jié)變成雙字節(jié),高位填0）固定占用兩個(gè)字節(jié)僻族，所以，java中char類型的變量也是占用兩個(gè)字節(jié)屡谐。
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if (anObject instanceof String) {
String anotherString = (String)anObject;
int n = value.length;
if (n == anotherString.value.length) {
char v1[] = value;
char v2[] = anotherString.value;
int i = 0;
while (n-- != 0) {
if (v1[i] != v2[i])
return false;
i++;
}
return true;
}
}
return false;
}
此equals方法包含了"=="述么，雙等號(hào)比較的是地址，存儲(chǔ)地址相同愕掏，內(nèi)容則相同度秘。當(dāng)?shù)刂凡煌臅r(shí)候，先驗(yàn)證了比較對(duì)象是否為String饵撑，接著比較了兩個(gè)字符串的長(zhǎng)度剑梳，最后才循環(huán)比較每個(gè)字符是否相等。
Integer的equals和hashCode方法
@Override
public int hashCode() {
return Integer.hashCode(value);
}
//就是返回Integer對(duì)象里包含的那個(gè)整數(shù)的值
public static int hashCode(int value) {
return value;
}
public boolean equals(Object obj) {
if (obj instanceof Integer) {
return value == ((Integer)obj).intValue();
}
return false;
}
重寫(xiě)一個(gè)對(duì)象的hashcode
- 如果是boolean值滑潘，則計(jì)算 f ? 1:0垢乙；
- 如果是byte\char\short\int,則計(jì)算 (int)f；
- 如果是long值语卤，則計(jì)算 (int)(f ^ (f >>> 32))追逮；
- 如果是float值，則計(jì)算 Float.floatToIntBits(f)粹舵；
- 如果是double值钮孵，則計(jì)算 Double.doubleToLongBits(f)，然后返回的結(jié)果是long,再用規(guī)則(3)去處理long,得到int眼滤；
- 如果是對(duì)象應(yīng)用巴席，如果equals方法中采取遞歸調(diào)用的比較方式，那么hashCode中同樣采取遞歸調(diào)用hashCode的方式诅需。否則需要為這個(gè)域計(jì)算一個(gè)范式漾唉，比如當(dāng)這個(gè)域的值為null的時(shí)候睬关，那么hashCode 值為0；
- 如果是數(shù)組毡证，那么需要為每個(gè)元素當(dāng)做單獨(dú)的域來(lái)處理电爹。java.util.Arrays.hashCode 方法包含了8種基本類型數(shù)組和引用數(shù)組的hashCode計(jì)算，算法同上料睛。
最后再將每個(gè)域的散列碼相加
哈希碰撞（hash沖突）
- 再哈希法丐箩，就是出現(xiàn)沖突后采用其他的哈希函數(shù)計(jì)算，直到不再?zèng)_突為止恤煞。
- 鏈接地址法屎勘，是在出現(xiàn)沖突的地方存儲(chǔ)一個(gè)鏈表，所有的同義詞記錄都存在其中居扒。形象點(diǎn)說(shuō)就行像是在出現(xiàn)沖突的地方直接把后續(xù)的值摞上去概漱。例如HashMap結(jié)構(gòu)。
這很容易理解喜喂，因?yàn)樽鳛橐环N可用的散列算法瓤摧，其位數(shù)一定是有限的，也就是說(shuō)它能記錄的文件是有限的——而文件數(shù)量是無(wú)限的玉吁，兩個(gè)文件指紋發(fā)生碰撞的概率永遠(yuǎn)不會(huì)是零照弥。
哈希算法
- 求模（%） 但單純使用求模算法計(jì)算之后的結(jié)果帶有明顯的規(guī)律性，這種規(guī)律將導(dǎo)致算法將能難保證不可逆性进副。
- 異或（^） 再配合移位等運(yùn)算
流行的hash算法包括 MD5（已被證明不具有強(qiáng)抗碰撞性）这揣、SHA-1 和 SHA-256（碰撞時(shí)開(kāi)銷更大）
一個(gè)小例子，拍賣會(huì)一個(gè)人只能出一次價(jià)影斑，大家都出好好给赞，價(jià)高者得，避免數(shù)據(jù)提交后有人知道后作弊：最高價(jià)+1 這種情況發(fā)生矫户，每個(gè)人只需要提交自己出價(jià)的hash值即可片迅，等到公布后再拿出原價(jià)與hash值對(duì)應(yīng)即可。
hash環(huán)（一致性hash算法）
先構(gòu)造一個(gè)長(zhǎng)度為232的整數(shù)環(huán)（這個(gè)環(huán)被稱為一致性Hash環(huán)）吏垮，根據(jù)節(jié)點(diǎn)名稱的Hash值（其分布為[0, 232-1]）將服務(wù)器節(jié)點(diǎn)放置在這個(gè)Hash環(huán)上障涯，然后根據(jù)數(shù)據(jù)的Key值計(jì)算得到其Hash值（其分布也為[0, 232-1]），接著在Hash環(huán)上順時(shí)針查找距離這個(gè)Key值的Hash值最近的服務(wù)器節(jié)點(diǎn)膳汪，完成Key到服務(wù)器的映射查找唯蝶。 ////這種算法解決了普通余數(shù)Hash算法伸縮性差的問(wèn)題，可以保證在上線遗嗽、下線服務(wù)器的情況下盡量有多的請(qǐng)求命中原來(lái)路由到的服務(wù)器粘我。
- list+排序
算出所有節(jié)點(diǎn)的hash值放入數(shù)組或集合（方便擴(kuò)展）中，從小到大排列；之后征字，等待路由的一方都弹，算出自己的hash，然后從list中找到第一hash值大于自己的節(jié)點(diǎn)即可匙姜，倘若沒(méi)有畅厢，意味此hash值大于所有節(jié)點(diǎn)的hash值，那么選list(0)氮昧，即最小的那個(gè)即可框杜。 - 遍歷+list
- 服務(wù)器節(jié)點(diǎn)不排序，其Hash值全部直接放入一個(gè)List中
- 待路由的節(jié)點(diǎn)袖肥，算出其Hash值咪辱，由于指明了"順時(shí)針"(指的list的順時(shí)針)，因此遍歷List椎组，比待路由的節(jié)點(diǎn)Hash值大的油狂，算出差值并記錄，比待路由節(jié)點(diǎn)Hash值小的忽略寸癌。
- 算出所有的差值之后专筷，最小的那個(gè)，就是最終需要路由過(guò)去的節(jié)點(diǎn)灵份。
- 二叉查找樹(shù)
當(dāng)然我們不能簡(jiǎn)單地使用二叉查找樹(shù)仁堪，因?yàn)榭赡艹霈F(xiàn)不平衡的情況。平衡二叉查找樹(shù)有AVL樹(shù)填渠、紅黑樹(shù)等，這里使用紅黑樹(shù)鸟辅，選用紅黑樹(shù)的原因有兩點(diǎn)：
- 紅黑樹(shù)主要的作用是用于存儲(chǔ)有序的數(shù)據(jù)氛什，這其實(shí)和第一種解決方案的思路又不謀而合了，但是它的效率非常高
- JDK里面提供了紅黑樹(shù)的代碼實(shí)現(xiàn)TreeMap和TreeSet
另外匪凉，以TreeMap為例枪眉，TreeMap本身提供了一個(gè)tailMap(K fromKey)方法，支持從紅黑樹(shù)中查找比f(wàn)romKey大的值的集合再层，但并不需要遍歷整個(gè)數(shù)據(jù)結(jié)構(gòu)贸铜。
使用紅黑樹(shù)，可以使得查找的時(shí)間復(fù)雜度降低為O(logN)聂受，比上面兩種解決方案蒿秦，效率大大提升。
設(shè)置虛擬節(jié)點(diǎn)
String重寫(xiě)的hashCode()方法在一致性Hash算法中實(shí)用價(jià)值不大蛋济，因?yàn)橛袝r(shí)服務(wù)器節(jié)點(diǎn)ip間差別很小棍鳖，String的hash計(jì)算方式導(dǎo)致其值也差距小。得找個(gè)算法重新計(jì)算HashCode碗旅。這種重新計(jì)算Hash值的算法有很多渡处，比如CRC32_HASH镜悉、FNV1_32_HASH（計(jì)算效率會(huì)高一些）、KETAMA_HASH（是默認(rèn)的MemCache推薦的一致性Hash算法）医瘫。
/**
* 帶虛擬節(jié)點(diǎn)的一致性Hash算法
* @author 五月的倉(cāng)頡 http://www.cnblogs.com/xrq730/
*/
public class ConsistentHashingWithVirtualNode
{
/**
* 待添加入Hash環(huán)的服務(wù)器列表
*/
private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
"192.168.0.3:111", "192.168.0.4:111"};
/**
* 真實(shí)結(jié)點(diǎn)列表,考慮到服務(wù)器上線侣肄、下線的場(chǎng)景，即添加醇份、刪除的場(chǎng)景會(huì)比較頻繁稼锅，這里使用LinkedList會(huì)更好
*/
private static List<String> realNodes = new LinkedList<String>();
/**
* 虛擬節(jié)點(diǎn)，key表示虛擬節(jié)點(diǎn)的hash值被芳，value表示虛擬節(jié)點(diǎn)的名稱
*/
private static SortedMap<Integer, String> virtualNodes =
new TreeMap<Integer, String>();
/**
* 虛擬節(jié)點(diǎn)的數(shù)目缰贝，這里寫(xiě)死，為了演示需要畔濒，一個(gè)真實(shí)結(jié)點(diǎn)對(duì)應(yīng)5個(gè)虛擬節(jié)點(diǎn)
*/
private static final int VIRTUAL_NODES = 5;
static
{
// 先把原始的服務(wù)器添加到真實(shí)結(jié)點(diǎn)列表中
for (int i = 0; i < servers.length; i++)
realNodes.add(servers[i]);
// 再添加虛擬節(jié)點(diǎn)剩晴，遍歷LinkedList使用foreach循環(huán)效率會(huì)比較高
for (String str : realNodes)
{
for (int i = 0; i < VIRTUAL_NODES; i++)
{
String virtualNodeName = str + "&&VN" + String.valueOf(i);
int hash = getHash(virtualNodeName);
System.out.println("虛擬節(jié)點(diǎn)[" + virtualNodeName + "]被添加, hash值為" + hash);
virtualNodes.put(hash, virtualNodeName);
}
}
System.out.println();
}
/**
* 使用FNV1_32_HASH算法計(jì)算服務(wù)器的Hash值,這里不使用重寫(xiě)hashCode的方法，最終效果沒(méi)區(qū)別
*/
private static int getHash(String str)
{
final int p = 16777619;
int hash = (int)2166136261L;
for (int i = 0; i < str.length(); i++)
hash = (hash ^ str.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
// 如果算出來(lái)的值為負(fù)數(shù)則取其絕對(duì)值
if (hash < 0)
hash = Math.abs(hash);
return hash;
}
/**
* 得到應(yīng)當(dāng)路由到的結(jié)點(diǎn)
*/
private static String getServer(String node)
{
// 得到帶路由的結(jié)點(diǎn)的Hash值
int hash = getHash(node);
// 得到大于該Hash值的所有Map
SortedMap<Integer, String> subMap =
virtualNodes.tailMap(hash);
// 第一個(gè)Key就是順時(shí)針過(guò)去離node最近的那個(gè)結(jié)點(diǎn)
Integer i = subMap.firstKey();
// 返回對(duì)應(yīng)的虛擬節(jié)點(diǎn)名稱侵状，這里字符串稍微截取一下
String virtualNode = subMap.get(i);
return virtualNode.substring(0, virtualNode.indexOf("&&"));
}
public static void main(String[] args)
{
String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
for (int i = 0; i < nodes.length; i++)
System.out.println("[" + nodes[i] + "]的hash值為" +
getHash(nodes[i]) + ", 被路由到結(jié)點(diǎn)[" + getServer(nodes[i]) + "]");
}
}
