?

首先，我們要知道set是利使用map是實(shí)現(xiàn)的，因?yàn)橹灰胢ap中的key唯一性就行了。

1.hashmap 和hashtable的區(qū)別是什么？

我們可以背出：? hashtable線程安全。hashmap不安全。

??????????????????????? hashmap中key 和value可以為空，當(dāng)然根據(jù)唯一性，只能有一個(gè)key為null;

?????????????????????? 還有呢，hash函數(shù)不同下面再談）

2.我們?cè)谥R(shí)點(diǎn)回顧中，對(duì)于一個(gè)hash函數(shù)，有哪些方法，如何解決沖突/

?除留余數(shù)法（最常用）,平方取中，隨機(jī)數(shù)法

開放地址法，拉鏈法

3、那么hashmap中和hashtablehash函數(shù)是什么呢？如何解決沖突的呢。

解決沖突是拉鏈法，就是加鏈表。

那么hash函數(shù)呢，

hashmap 比較高級(jí)，我們看hashmap,如果你復(fù)習(xí)一下數(shù)據(jù)結(jié)構(gòu)，在哈希表中，他會(huì)告訴你，一個(gè)hash表就是個(gè)數(shù)組，這個(gè)數(shù)組有大小，同時(shí)還有裝載因子，

size*loadFactor就是我們能存元素個(gè)數(shù)的最大值，這個(gè)值叫做閾（yu）值,超過這個(gè)值，就會(huì)resize，意思就是重新擴(kuò)張數(shù)組，然后對(duì)老元素重新hash，所以resize很費(fèi)時(shí)。

hashmap在size上下了功夫，他把數(shù)組的大小設(shè)置為2的n次方，初始為16.，如果不夠用就成2倍擴(kuò)張。為什么設(shè)置為2的n次方呢？

這樣可以充分利用位運(yùn)算的優(yōu)勢(shì)。比如 a*2? 表示成? a<<1，?那么 a%16=a&1?5=a&(1111)=a的二級(jí)制的后面4為，在位圖中我們a%32=a&31

其實(shí)如果我們看 a&1=a%2? a&3=a%4? 好了，下面我們看看它的hash函數(shù)吧

static int indexFor(int h, int length) {return h & (length-1);}

?看到?jīng)]有直接風(fēng)騷的使用h&(length-1)而且length是2的倍數(shù)。其實(shí)就是h%(length)

慢著，這個(gè)函數(shù)有什么缺陷呢？當(dāng)size比較小的時(shí)候，比如32的時(shí)候，也就是(11111)，最后根據(jù)key確定位置的時(shí)候，是根據(jù)key的后5位確定的，而key，函數(shù)中使用h表示，是int型啊，32位的數(shù)只能通過后五位確定，這樣沖突會(huì)很多，我們希望32位的每一位都被考慮進(jìn)來。都可以決定key的位置，于是，

1 static int hash(int h) { 2 // This function ensures that hashCodes that differ only by 3 // constant multiples at each bit position have a bounded 4 // number of collisions (approximately 8 at default load factor). 5 h ^= (h >>> 20) ^ (h >>> 12); 6 return h ^ (h >>> 7) ^ (h >>> 4); 7 }

我們看到了，這個(gè)復(fù)雜的代碼，它的意思就是我剛才說的，通過移位和異或讓更多的位決定key的位置，這樣會(huì)減少?zèng)_突，更均勻。

但是hashtable，雖說是線程安全的，但是他是jdk1.0引入的很老，它的hash函數(shù)很普通，

int?index?=?(hash?&?0x7FFFFFFF)?%?tab.length; //hash就是key的hashcode,然后獲得非符號(hào)位（hashcode為 int,可能為負(fù)，所以去掉符號(hào)位）；

對(duì)于線程安全，以后再仔細(xì)說。

?

?

?

?

?

?

?

?

?

?

?

?

?

http://zhangshixi.iteye.com/blog/672697

?

???????????????

?

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

總結(jié)

以上是生活随笔為你收集整理的Hash(4) hashtable,hashmap的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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