本文非原創(chuàng)，來源：https://www.cnblogs.com/renlong0602/p/4206455.html
1.Hash表的結(jié)構(gòu)
首先灰羽，允許我們花一點時間來簡單介紹hash表躏精。
什么是hash表
hash表是一種二維結(jié)構(gòu)渣刷，管理著一對對<Key,Value>這樣的鍵值對,Hash表的結(jié)構(gòu)如下圖所示：
如上圖所示，左側(cè)部分是一個一維順序存儲的數(shù)組矗烛，數(shù)組單元格里的內(nèi)容是指向另一個鏈?zhǔn)綌?shù)組的指針辅柴。圖中綠色部分是<Key,Value>，綠色部分右側(cè)的白色部分是指向下一對鍵值對的指針瞭吃。
hash表的工作原理：
（1）.第一步 先根據(jù)給定的key和散列算法得到具體的散列值碌嘀，也就是對應(yīng)的數(shù)組下標(biāo)。
（2）.第二步虱而，根據(jù)數(shù)組下標(biāo)得到此下標(biāo)里存儲的指針筏餐，若指針為空，則不存在這樣的鍵值對牡拇，否則根據(jù)此指針得到此鏈?zhǔn)綌?shù)組魁瞪。（此鏈?zhǔn)綌?shù)組里存放的均為一對對<Key,Value>）穆律。
（3）.遍歷此鏈?zhǔn)綌?shù)組，分別取出Key與給定的Key比較导俘，若找到與給定key相等的Key峦耘，即在此hash表中存在此要查找的<Key,Value>鍵值對，此后便可以對此鍵值對進(jìn)行相關(guān)操作旅薄；若找不到辅髓，即為不存在此 鍵值對。
所以hash表其實就是管理一對對<Key少梁，Value>這樣的結(jié)構(gòu)
2.不可避免的hash沖突
總所周知洛口，hash表是管理著一組組的<key,Value>的數(shù)據(jù)結(jié)構(gòu)，訪問時對Key采取散列算法求值凯沪，根據(jù)此值得到鏈?zhǔn)綌?shù)組第焰，根據(jù)鏈?zhǔn)綌?shù)組取得Value.那對一個給定的Key是怎么的呢？
散列技術(shù)基于散列算法妨马，理想情況下是將相同的key散列為相同的值挺举，不同的key散列為不同的值。但是實際情況下烘跺，因為存儲空間有限湘纵，使得這種算法是不可能被實現(xiàn)的，所以當(dāng)不同的key被散列為相同的值時滤淳，便產(chǎn)生了沖突梧喷。這就是我們所說的hash沖突，下面我們來談一談為什么這種算法是不可能實現(xiàn)的娇钱？
理想情況下一維的hash表 ：如下圖：
理想情況下的一維hash表存放的是一對對<key伤柄，Value>鍵值，
1.對hash散列算法的要求：不同的Key必須散列為不同的值文搂，相同的Key必須散列為相同的值适刀。
2.對數(shù)組的要求，為了保持訪問的高效煤蹭，必須保持為順序存儲的數(shù)組笔喉。（鏈?zhǔn)綌?shù)組的訪問時間為logn，而且還必須時刻維持平衡樹的結(jié)構(gòu)代價較大硝皂，不符合要求）常挚。
OK....那么問題來了，理想情況下的hash表能完美解決以下問題嗎：
（1）.為了高效稽物，你是順序存儲的數(shù)組奄毡，那么你知道你每次需要開辟多大的存儲給此數(shù)組嗎？如果太大贝或，勢必會造成空間的浪費(fèi)吼过，而且此空間還必須是連續(xù)的锐秦，如果過小，需要不斷調(diào)整盗忱。這樣你還能維持高效嗎酱床？
（2）.針對每個<Key,Value>你又準(zhǔn)備多大的空間去存儲此鍵值對呢？很遺憾的告訴你...你不知道趟佃。過大過小都會面對剛才我們提出的問題扇谣？
問題出現(xiàn)后，總會有那么幾個天才冒出來闲昭？
3.hash表的完美實現(xiàn)（允許沖突的存在）
hash查找是一種高效的查找罐寨，在存儲空間和查找時間的相互妥協(xié)下，有人提出來了一種新的想法汤纸，即允許將不同的key散列為相同的值衩茸。
具體實現(xiàn)如下：
1.先在空間中開辟一個數(shù)組。我們首先根據(jù)key和散列算法取得數(shù)組的下標(biāo)贮泞，也就是上圖部分的左側(cè)數(shù)組。
2.數(shù)組中的每個單元格維持著一個鏈?zhǔn)綌?shù)組幔烛，鏈?zhǔn)綌?shù)組里存放<Key,Value>.
3.訪問的時候啃擦，根據(jù)key一一比較，若找到饿悬，取得到value令蛉，若找不到，不同的編程語言返回著不同的值.
4.存儲的時候狡恬，先查找此key是否存在珠叔，若存在則修改此Value值，若不存在弟劲，則在此鏈?zhǔn)綌?shù)組的尾部加上一個一對<Key,Value>;
有以上我們可以看出祷安，利用hash表存儲對象，查詢的時候速度是非惩闷颍快的汇鞭。左側(cè)數(shù)組可以隨機(jī)訪問，右側(cè)鏈?zhǔn)綌?shù)組雖然需要遍歷庸追，但是如果散列算法夠出色的話霍骄，每個鏈?zhǔn)綌?shù)組存儲的鍵值對數(shù)量就會很小。查找的速度也足夠快淡溯。理想情況下查找速度幾乎可以達(dá)到o(1)读整。
2.JavaScript中對象的存儲形式？
1.兩種創(chuàng)建對象的區(qū)別
（1）.用構(gòu)造函數(shù)創(chuàng)建對象
var object=new Object();
object.x=1;
object.2=1; //出錯咱娶，因為變量不能以數(shù)字開頭..
以上的錯誤相信大家都知道米间，那么用字面量創(chuàng)建對象呢煎楣？
（2）.用字面量創(chuàng)建對象
var object = {
x: 1,
2: 2
};//不會報錯
（3）兩種方式比較
兩則相比，大家不覺得奇怪嗎车伞？------為什么第一種方式報錯择懂，第二種反而不會？
當(dāng)然你也可以理解為JS引擎對語法錯誤的屏蔽.那么JS引擎干嘛要費(fèi)那么大的勁去屏蔽違法的變量呢另玖？答案就是：---事出必有因
假設(shè)JS允許通過下面這種方式賦值或者訪問：
object.2=2; //假設(shè)不會出錯
2==2;
console.log(2); //那么出現(xiàn)這種方式的時候困曙，你讓JS引擎怎么辦？是把2當(dāng)做全局變量理解還是數(shù)字2
當(dāng)出現(xiàn)這樣的情況谦去，解釋器也只能干瞪眼了.所以為了語法的統(tǒng)一慷丽，才對以變量的形式的訪問對象的變量定義了各種要求，
也就是說鳄哭，js引擎對于違法變量的屏蔽是合理的要糊。
那么問題又來了----
//既然，對變量的形式規(guī)定了要求妆丘，那么又干嘛允許這種玩意存在呢锄俄？-----答案就是：因為它也是合理的/
var object = {
x：1,
2: 2
};
為什么上面這種方式合理呢？
因為在hash表的<Key,Value>鍵值對中并沒有對key提出這樣或者那樣的要求勺拣。所以奶赠，如果JS對象是基于Hash表存儲變量的，既然在存儲時這種形式合法药有，那么你又為什么不允許我訪問我存儲的變量呢毅戈？ 這不是自相矛盾嗎！
當(dāng)然愤惰，這里有一個邏輯性的問題苇经，我為什么認(rèn)同JS對象的存儲是基于Hash的呢？（這點在第三部分我會給出解釋）
以上列舉了兩種定義對象變量方法以及區(qū)別宦言，進(jìn)而解釋了為什么兩種定義形式明明相互沖突卻又同時存在扇单！
下面開始我們的討論： JS對象在hash表中Key到底是什么？------答案：字符串
首先來看一下他的輸出結(jié)果：
var object = {
x: 1,
2: 2
}
for (var property in object) {
console.log('(' + typeof property + ')' + property + ':' + object[property]);
}
//結(jié)果 (string)2:2
// (string)x:1
以上的代碼證明了兩點： object[2]是真的存在的..并且<Key,Value>中的key是以字符串的形式存在蜡励。也就是說令花，對象的變量和值作為<Key,Value>鍵值對存儲在hash表中,key是以字符串的形式存在,那么value是以什么形式存在呢？ 這點我們以后再討論凉倚。也很值得討論兼都。
總結(jié)：
用字面量初始化的對象的時候，變量名可以使數(shù)字稽寒，也可以是字符串扮碧，但是不可以是對象(下面會給出解釋)， 但是以后用[]訪問的時候，[]中的內(nèi)容則可以是對象慎王，只要[]中內(nèi)容可以轉(zhuǎn)換為字符串就可以蚓土。
初始化對象的兩種形式都是合法的，但是在以.號訪問變量時只能訪問我們平時所說的合法變量赖淤，以[]訪問時則比較自由蜀漆，也沒有那么多的要求，這是JS設(shè)計時候存在的缺點咱旱，但同時也是JS語言的有點确丢。
為什么對象初始化的時候不能用對象作為變量，如下所示吐限，：
var object={
{x:1}:2 //這種形式是錯誤的鲜侥，因為解釋器不能正確識別這種語法，會報錯诸典。-----理論上是可以做到的描函，可能是設(shè)計的時候存在的缺陷。
}
//以下的方式則不會報錯
var object={};
object[{x:1}]=1;
console.log(object[{x:1}]) ;//1 解釋器會盡力量把[]中的內(nèi)容解釋成字符串狐粱。
知道看Key是字符串舀寓，那么我們現(xiàn)在可以解釋這個問題了：object[2]和object["2"]有區(qū)別嗎？-----（沒有脑奠，當(dāng)然基公，關(guān)于這點也得看你怎么理解）！為了證明這兩種形式?jīng)]有區(qū)別我們看下面兩個例子
請思考：用[]訪問對象變量的時候宋欺，解釋器幫我們都干了什么？
var object = {
x: 1,
2: 2
}
console.log(object[2]);//2
console.log(object["2"]);//2
object[2]=3;
console.log(object["2"]);//3
之所以object[2]和object["2"]等效胰伍，那是因為解釋器幫我們干了一點活齿诞，那么解釋器幫我們干了什么呢？
解釋器在訪問object[2]的時候骂租，先將方括號里面的2轉(zhuǎn)換成字符串祷杈。然后再訪問，為了證明這點渗饮，我寫了一點代碼證明這點但汞。
var object = {
x: 1,
2: 2
}
Object.prototype.toString = function () {
return '2';
}
console.log(object[{x: 1}]); //2
console.log(object["2"]); //2
console.log(object[2]); //2
下面花一點時間來分析上述代碼的執(zhí)行過程：
1.首先定義并初始化了一個object對象,對象中存在兩個變量。
2.重寫了Object原型中的toString()方法互站。
3.第7行輸出時對于[]中我們用了一個臨時的對象{x:1}私蕾。此對象被初始化后,在object[]執(zhí)行時，先分析方括號中{x:1}胡桃，此時解釋器為了將此對象轉(zhuǎn)換為字符串踩叭，如果是引用類型會調(diào)用原型對象中的toString()函數(shù)，如果是基本數(shù)據(jù)類型是也會將基本數(shù)據(jù)類型轉(zhuǎn)化為對應(yīng)字符串，結(jié)果即是訪問object["2"].輸出的結(jié)果也就是2了容贝。
所以我們也間接證明了JS對象中自脯，所有的key都是字符串，即使你訪問的時候不是字符串的形式斤富，解釋器也會盡力先將其轉(zhuǎn)化為字符串膏潮。
所以下面兩種方式初始化對象是完全等效的：
var object1 = {
x: 1,
1: 2
} //第一種
var object2 = {
'x': 1,
'1': 2
} //第二種
以上我們討論的是 JS對象的存儲形式以及數(shù)據(jù)是怎么存放的。
下面我們討論满力，為什么說JS中對象存儲的變量是基于hash的焕参。
3.JavaScript中的對象基于Hash表存儲變量。
（1）.證明：
我們可以隨時給一個對象增加或刪除變量（如果此變量允許刪除的話）
var object={};
object.x=1;//增加一個變量
delete object.x;//刪除一個變量 success
console.log(Object.keys(object).length); //0
（1） 既然變量的對象類型和個數(shù)是可變的脚囊，我們也就不能像java龟糕，c++那樣，先將一個對象分配固定的空間悔耘。JS的引用指向的對象所占用的空間必須支持隨時調(diào)整讲岁。基于此衬以，順序存儲的數(shù)組已經(jīng)被淘汰缓艳。
（2）鏈?zhǔn)綌?shù)組查詢較慢的弊端已經(jīng)先天決定其不可能作為對象中變量的存儲結(jié)構(gòu)。
（3）當(dāng)然你可以說看峻，我可以用樹的存儲結(jié)構(gòu)阶淘，效率較高的可能就是平衡樹了。平衡樹在查詢的時候時間復(fù)雜度為log(n),也不算太高互妓，但是當(dāng)刪除屬性的時候溪窒，平衡樹在調(diào)整的時候代價相比 于hash表也是很大》朊悖或許澈蚌，你還有其他的選擇，但是我敢說灼狰，肯定沒有任何一種有hash表存儲數(shù)據(jù)那么方便和高效宛瞄。
（4）.只有JavaScript的對象是基于hash表存儲的，那么所有的在c++,java交胚，c#中存在的不合理才會在JavaScript語言中變得合理份汗。
其實說白一點，物理存儲并非非hash表不可蝴簇，只是沒有比hash表更好的了杯活，所以在JS語言設(shè)計的時候就是當(dāng)做hash表結(jié)構(gòu)進(jìn)行設(shè)計的。
為了證明對象是基于hash表以鍵值對存儲的军熏，我們來簡單看一下數(shù)組類型和函數(shù)：
函數(shù)：
var person=function y(){};
person.x=1;
person.y=2;
for(var property in person){
console.log(property+" : "+ person[property])
}//x：1
// y:2
var array=[1,2,4]
for(var property in array){
console.log(property+" : "+ array[property])
}// 0: 1
// 1: 2
// 2：4
（2）.理解了這些有什么用：
1.你還會對數(shù)組數(shù)可以擁有屬性轩猩，函數(shù)也可以擁有屬性奇怪嗎？ 因為他們本身管理著屬于自己的hash表，所以他們隨時都可以給自己添加或則刪除一些屬性均践。
2.我們知道數(shù)組中的下表是可以隨意添加的晤锹，無論你設(shè)置為多大，你也可以越界訪問（嚴(yán)格來說彤委，根本就沒有所謂的越界）鞭铆，只是返回的結(jié)果是undefined...因為沒有找到對應(yīng)的key。
你將其理解為下標(biāo)焦影，倒不如理解為Key车遂，如此，JS數(shù)組還有那么神秘嗎斯辰？ 說白了舶担，也就是一種hash結(jié)構(gòu)。如果你想彬呻，你也可以把object當(dāng)成數(shù)組衣陶，然后自定義一整套函數(shù)，只是可能沒有那么方便闸氮。
注：當(dāng)然剪况，函數(shù)作為一種對象肯定有其的特殊性。在這里我們就不過多的討論了蒲跨。
4.JS對象是基于Hash表的典型應(yīng)用
var array=['true',true,false,'1',1,'','sss'," ",1,34,,,{x:1},{x:2}]
Array.prototype.unique=function(){
//利用對象的hash存儲特性去重
var object={},result=[];
for(var i=0,length=this.length;i<length;i++){
var temp=this[i],key;
if((typeof temp)=='object'){
key=JSON.stringify(temp); //若為對象類型译断，將對象序列化為字符串
} else{
key=typeof temp+temp;
}
if(!object[key]){
object[key]=true; //若object中已經(jīng)存在此鍵值，則證明此元素在數(shù)組中已經(jīng)存在
result.push(temp);
}
}
return result;
}
console.log(array.unique());
//["true", true, false, "1", 1, "", "sss", " ", 34, undefined, Object { x=1}, Object { x=2}]
此算法的缺點或悲，因為另外建立一個object對象和result數(shù)組孙咪，所以比較占用空間，但是速度非逞灿铮快该贾，至少比用樹形結(jié)構(gòu)快。這是對網(wǎng)上一些算法的改進(jìn)捌臊，網(wǎng)絡(luò)上有好多針對對象hash的算法并不能完美的去重。
比如數(shù)組[1,"1"兜材，{x:1},{x:2}]理澎。
文章中存在的疑點： Number,Boolean 等基本類型在轉(zhuǎn)化為字符串的時候到底調(diào)用的是什么方法？（不是原型鏈中的toString()方法曙寡，關(guān)于這點未能敘述糠爬，歡迎補(bǔ)充）
