---

1.Hash表的結(jié)構(gòu)

?

首先，允許我們花一點(diǎn)時(shí)間來簡單介紹hash表。

1.什么是hash表

hash表是一種二維結(jié)構(gòu)，管理著一對對<Key,Value>這樣的鍵值對,Hash表的結(jié)構(gòu)如下圖所示：

?

如上圖所示，左側(cè)部分是一個(gè)一維順序存儲(chǔ)的數(shù)組，數(shù)組單元格里的內(nèi)容是指向另一個(gè)鏈?zhǔn)綌?shù)組的指針。圖中綠色部分是<Key,Value>，綠色部分右側(cè)的白色部分是指向下一對鍵值對的指針。

hash表的工作原理：

?（1）.第一步 先根據(jù)給定的key和散列算法得到具體的散列值，也就是對應(yīng)的數(shù)組下標(biāo)。

?（2）.第二步，根據(jù)數(shù)組下標(biāo)得到此下標(biāo)里存儲(chǔ)的指針，若指針為空，則不存在這樣的鍵值對，否則根據(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表其實(shí)就是管理一對對<Key，Value>這樣的結(jié)構(gòu)。

?

2.不可避免的hash沖突

總所周知，hash表是管理著一組組的<key,Value>的數(shù)據(jù)結(jié)構(gòu)，訪問時(shí)對Key采取散列算法求值，根據(jù)此值得到鏈?zhǔn)綌?shù)組，根據(jù)鏈?zhǔn)綌?shù)組取得Value.那對一個(gè)給定的Key是怎么的呢？

? ? ? 散列技術(shù)基于散列算法，理想情況下是將相同的key散列為相同的值，不同的key散列為不同的值。但是實(shí)際情況下，因?yàn)榇鎯?chǔ)空間有限，使得這種算法是不可能被實(shí)現(xiàn)的，所以當(dāng)不同的key被散列為相同的值時(shí)，便產(chǎn)生了沖突。這就是我們所說的hash沖突，下面我們來談一談為什么這種算法是不可能實(shí)現(xiàn)的？

? ? ? 理想情況下一維的hash表 ：如下圖：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??　　　　　　　　　　　　　　　　　　 （2）理想情況下的一維hash表

理想情況下的一維hash表存放的是一對對<key，Value>鍵值，

1.對hash散列算法的要求：不同的Key必須散列為不同的值，相同的Key必須散列為相同的值。

2.對數(shù)組的要求，為了保持訪問的高效，必須保持為順序存儲(chǔ)的數(shù)組。（鏈?zhǔn)綌?shù)組的訪問時(shí)間為logn，而且還必須時(shí)刻維持平衡樹的結(jié)構(gòu)代價(jià)較大，不符合要求）。

OK....那么問題來了，理想情況下的hash表能完美解決以下問題嗎：

（1）.為了高效，你是順序存儲(chǔ)的數(shù)組，那么你知道你每次需要開辟多大的存儲(chǔ)給此數(shù)組嗎？如果太大，勢必會(huì)造成空間的浪費(fèi)，而且此空間還必須是連續(xù)的，如果過小，需要不斷調(diào)整。這樣你還能維持高效嗎？

（2）.針對每個(gè)<Key,Value>你又準(zhǔn)備多大的空間去存儲(chǔ)此鍵值對呢？很遺憾的告訴你...你不知道。過大過小都會(huì)面對剛才我們提出的問題？

?

問題出現(xiàn)后，總會(huì)有那么幾個(gè)天才冒出來？

?

3.hash表的完美實(shí)現(xiàn)（允許沖突的存在）

hash查找是一種高效的查找，在存儲(chǔ)空間和查找時(shí)間的相互妥協(xié)下，有人提出來了一種新的想法，即允許將不同的key散列為相同的值。

具體實(shí)現(xiàn)如下：

1.先在空間中開辟一個(gè)數(shù)組。我們首先根據(jù)key和散列算法取得數(shù)組的下標(biāo)，也就是上圖部分的左側(cè)數(shù)組。

2.數(shù)組中的每個(gè)單元格維持著一個(gè)鏈?zhǔn)綌?shù)組，鏈?zhǔn)綌?shù)組里存放<Key,Value>.

3.訪問的時(shí)候，根據(jù)key一一比較，若找到，取得到value，若找不到，不同的編程語言返回著不同的值.

4.存儲(chǔ)的時(shí)候，先查找此key是否存在，若存在則修改此Value值，若不存在，則在此鏈?zhǔn)綌?shù)組的尾部加上一個(gè)一對<Key,Value>;

有以上我們可以看出，利用hash表存儲(chǔ)對象，查詢的時(shí)候速度是非常快的。左側(cè)數(shù)組可以隨機(jī)訪問，右側(cè)鏈?zhǔn)綌?shù)組雖然需要遍歷，但是如果散列算法夠出色的話，每個(gè)鏈?zhǔn)綌?shù)組存儲(chǔ)的鍵值對數(shù)量就會(huì)很小。查找的速度也足夠快。理想情況下查找速度幾乎可以達(dá)到o(1)。

?

?

2.JavaScript中對象的存儲(chǔ)形式？

?1.兩種創(chuàng)建對象的區(qū)別

?（1）.用構(gòu)造函數(shù)創(chuàng)建對象

1 var object=new Object(); 2 object.x=1; 3 object.2=1; //出錯(cuò)，因?yàn)樽兞坎荒芤詳?shù)字開頭..

?以上的錯(cuò)誤相信大家都知道，那么用字面量創(chuàng)建對象呢？

（2）.用字面量創(chuàng)建對象

var object = {x: 1,2: 2 };//不會(huì)報(bào)錯(cuò)

---

?

（3）兩種方式比較

兩則相比，大家不覺得奇怪嗎？------為什么第一種方式報(bào)錯(cuò)，第二種反而不會(huì)？

?當(dāng)然你也可以理解為JS引擎對語法錯(cuò)誤的屏蔽.那么JS引擎干嘛要費(fèi)那么大的勁去屏蔽違法的變量呢？答案就是：---事出必有因

?

假設(shè)JS允許通過下面這種方式賦值或者訪問

object.2=2; //假設(shè)不會(huì)出錯(cuò) 2==2;
console.log(2);//那么出現(xiàn)這種方式的時(shí)候，你讓JS引擎怎么辦？是把2當(dāng)做全局變量理解還是數(shù)字2

當(dāng)出現(xiàn)這樣的情況，解釋器也只能干瞪眼了.所以為了語法的統(tǒng)一，才對以變量的形式的訪問對象的變量定義了各種要求，

也就是說，js引擎對于違法變量的屏蔽是合理的。

?

那么問題又來了----

//既然，對變量的形式規(guī)定了要求，那么又干嘛允許這種玩意存在呢？-----答案就是：因?yàn)樗彩呛侠淼? var object = {
x：1,2: 2 };

為什么上面這種方式合理呢？

　　因?yàn)樵趆ash表的<Key,Value>鍵值對中并沒有對key提出這樣或者那樣的要求。所以，如果JS對象是基于Hash表存儲(chǔ)變量的，既然在存儲(chǔ)時(shí)這種形式合法，那么你又為什么不允許我訪問我存儲(chǔ)的變量呢？ 這不是自相矛盾嗎！

? ? ?當(dāng)然，這里有一個(gè)邏輯性的問題，我為什么認(rèn)同JS對象的存儲(chǔ)是基于Hash的呢？（這點(diǎn)在第三部分我會(huì)給出解釋）

?

以上列舉了兩種定義對象變量方法以及區(qū)別，進(jìn)而解釋了為什么兩種定義形式明明相互沖突卻又同時(shí)存在！

---

?

下面開始我們的討論： 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

以上的代碼證明了兩點(diǎn)： object[2]是真的存在的..并且<Key,Value>中的key是以字符串的形式存在。也就是說，對象的變量和值作為<Key,Value>鍵值對存儲(chǔ)在hash表中,key是以字符串的形式存在,那么value是以什么形式存在呢？ 這點(diǎn)我們以后再討論。也很值得討論。

?

總結(jié)：?

? ? ? ? ?用字面量初始化的對象的時(shí)候，變量名可以使數(shù)字，也可以是字符串，但是不可以是對象(下面會(huì)給出解釋)， 但是以后用[]訪問的時(shí)候，[]中的內(nèi)容則可以是對象，只要[]中內(nèi)容可以轉(zhuǎn)換為字符串就可以。

? ? ? ? ?初始化對象的兩種形式都是合法的，但是在以.號訪問變量時(shí)只能訪問我們平時(shí)所說的合法變量，以[]訪問時(shí)則比較自由，也沒有那么多的要求，這是JS設(shè)計(jì)時(shí)候存在的缺點(diǎn)，但同時(shí)也是JS語言的有點(diǎn)。

? 為什么對象初始化的時(shí)候不能用對象作為變量，如下所示，：?

var object={{x:1}:2 //這種形式是錯(cuò)誤的，因?yàn)榻忉屍鞑荒苷_識(shí)別這種語法，會(huì)報(bào)錯(cuò)。-----理論上是可以做到的，可能是設(shè)計(jì)的時(shí)候存在的缺陷。 }

//以下的方式則不會(huì)報(bào)錯(cuò)
var object={};
object[{x:1}]=1;
console.log(object[{x:1}]) ;//1 解釋器會(huì)盡力量把[]中的內(nèi)容解釋成字符串。

?

?

?

?

知道看Key是字符串，那么我們現(xiàn)在可以解釋這個(gè)問題了：object[2]和object["2"]有區(qū)別嗎？-----（沒有，當(dāng)然，關(guān)于這點(diǎn)也得看你怎么理解）！為了證明這兩種形式?jīng)]有區(qū)別我們看下面兩個(gè)例子

?

? ?請思考：用[]訪問對象變量的時(shí)候，解釋器幫我們都干了什么？

var object = {x: 1,2: 2 }console.log(object[2]);//2 console.log(object["2"]);//2object[2]=3; console.log(object["2"]);//3

之所以object[2]和object["2"]等效，那是因?yàn)榻忉屍鲙臀覀兏闪艘稽c(diǎn)活，那么解釋器幫我們干了什么呢？

?

解釋器在訪問object[2]的時(shí)候，先將方括號里面的2轉(zhuǎn)換成字符串。然后再訪問，為了證明這點(diǎn)，我寫了一點(diǎn)代碼證明這點(diǎ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

下面花一點(diǎn)時(shí)間來分析上述代碼的執(zhí)行過程：

1.首先定義并初始化了一個(gè)object對象,對象中存在兩個(gè)變量。

2.重寫了Object原型中的toString()方法。

3.第7行輸出時(shí)對于[]中我們用了一個(gè)臨時(shí)的對象{x:1}。此對象被初始化后,在object[]執(zhí)行時(shí)，先分析方括號中{x:1}，此時(shí)解釋器為了將此對象轉(zhuǎn)換為字符串，如果是引用類型會(huì)調(diào)用原型對象中的toString()函數(shù)，如果是基本數(shù)據(jù)類型是也會(huì)將基本數(shù)據(jù)類型轉(zhuǎn)化為對應(yīng)字符串，結(jié)果即是訪問object["2"].輸出的結(jié)果也就是2了。

?

所以我們也間接證明了JS對象中，所有的key都是字符串，即使你訪問的時(shí)候不是字符串的形式，解釋器也會(huì)盡力先將其轉(zhuǎn)化為字符串。

所以下面兩種方式初始化對象是完全等效的：

1 var object1 = { 2 x: 1, 3 1: 2 4 } //第一種 5 var object2 = { 6 'x': 1, 7 '1': 2 8 } //第二種

?

?以上我們討論的是 JS對象的存儲(chǔ)形式以及數(shù)據(jù)是怎么存放的。

---

?下面我們討論，為什么說JS中對象存儲(chǔ)的變量是基于hash的。

?

3.JavaScript中的對象基于Hash表存儲(chǔ)變量。?

（1）.證明：

? 我們可以隨時(shí)給一個(gè)對象增加或刪除變量（如果此變量允許刪除的話）

1 var object={}; 2 object.x=1;//增加一個(gè)變量 3 delete object.x;//刪除一個(gè)變量 success 4 console.log(Object.keys(object).length); //0

?（1） 既然變量的對象類型和個(gè)數(shù)是可變的，我們也就不能像java，c++那樣，先將一個(gè)對象分配固定的空間。JS的引用指向的對象所占用的空間必須支持隨時(shí)調(diào)整。基于此，順序存儲(chǔ)的數(shù)組已經(jīng)被淘汰。

?（2）鏈?zhǔn)綌?shù)組查詢較慢的弊端已經(jīng)先天決定其不可能作為對象中變量的存儲(chǔ)結(jié)構(gòu)。

?（3）當(dāng)然你可以說，我可以用樹的存儲(chǔ)結(jié)構(gòu)，效率較高的可能就是平衡樹了。平衡樹在查詢的時(shí)候時(shí)間復(fù)雜度為log(n),也不算太高，但是當(dāng)刪除屬性的時(shí)候，平衡樹在調(diào)整的時(shí)候代價(jià)相比　 ? ? ? ??于hash表也是很大。或許，你還有其他的選擇，但是我敢說，肯定沒有任何一種有hash表存儲(chǔ)數(shù)據(jù)那么方便和高效。

?（4）.只有JavaScript的對象是基于hash表存儲(chǔ)的，那么所有的在c++,java，c#中存在的不合理才會(huì)在JavaScript語言中變得合理。

? ? 其實(shí)說白一點(diǎn)，物理存儲(chǔ)并非非hash表不可，只是沒有比hash表更好的了，所以在JS語言設(shè)計(jì)的時(shí)候就是當(dāng)做hash表結(jié)構(gòu)進(jìn)行設(shè)計(jì)的。

?

為了證明對象是基于hash表以鍵值對存儲(chǔ)的，我們來簡單看一下數(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

數(shù)組：

var array=[1,2,4] for(var property in array){console.log(property+" : "+ array[property]) }// 0: 1
// 1: 2
// 2：4

（2）.理解了這些有什么用：

?1.你還會(huì)對數(shù)組數(shù)可以擁有屬性，函數(shù)也可以擁有屬性奇怪嗎？ 因?yàn)樗麄儽旧砉芾碇鴮儆谧约旱膆ash表，所以他們隨時(shí)都可以給自己添加或則刪除一些屬性。

?2.我們知道數(shù)組中的下表是可以隨意添加的，無論你設(shè)置為多大，你也可以越界訪問（嚴(yán)格來說，根本就沒有所謂的越界），只是返回的結(jié)果是undefined...因?yàn)闆]有找到對應(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)用

?

? 數(shù)組去重?

1 var array=['true',true,false,'1',1,'','sss'," ",1,34,,,{x:1},{x:2}] 2 3 Array.prototype.unique=function(){ 4 5 //利用對象的hash存儲(chǔ)特性去重 6 var object={},result=[]; 7 8 for(var i=0,length=this.length;i<length;i++){ 9 10 var temp=this[i],key; 11 12 if((typeof temp)=='object'){ 13 key=JSON.stringify(temp); //若為對象類型，將對象序列化為字符串 14 }else{ 15 key=typeof temp+temp; 16 } 17 18 if(!object[key]){ 19 object[key]=true; //若object中已經(jīng)存在此鍵值，則證明此元素在數(shù)組中已經(jīng)存在 20 result.push(temp); 21 22 } 23 24 } 25 26 return result; 27 28 } 29 30 console.log(array.unique()); //["true", true, false, "1", 1, "", "sss", " ", 34, undefined, Object { x=1}, Object { x=2}]

?

? //此算法的缺點(diǎn)，因?yàn)榱硗饨⒁粋€(gè)object對象和result數(shù)組，所以比較占用空間，但是速度非常快，至少比用樹形結(jié)構(gòu)快。這是對網(wǎng)上一些算法的改進(jìn)，網(wǎng)絡(luò)上有好多針對對象hash的算法并不能完美的去重。

　?比如數(shù)組[1,"1"，{x:1},{x:2}]。

?

文章中存在的疑點(diǎn)： Number,Boolean 等基本類型在轉(zhuǎn)化為字符串的時(shí)候到底調(diào)用的是什么方法？（不是原型鏈中的toString()方法，關(guān)于這點(diǎn)未能敘述，歡迎補(bǔ)充）;

?

轉(zhuǎn)載于:https://www.cnblogs.com/renlong0602/p/4206455.html

總結(jié)

以上是生活随笔為你收集整理的JavaScript系列-----对象基于哈希存储（Key，Value之Key篇） （1）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。