瑞客戀上數(shù)據(jù)結(jié)構(gòu)與算法第一季39課全課件

時(shí)間復(fù)雜度（平均添加、刪除、搜索Map MapKeyKeyMap那就是采取哈希表哈希表（Hash哈希表也叫做散列表（hash有“剁碎”的意思put("Jack",put("Rose",put("Kate",keyindex【O(1)indexO(1)

哈希函數(shù)

索數(shù)索數(shù)Bucket（桶），BucketsBucket （Hash key1≠key2，hash(key1)=索 數(shù)索 數(shù)

開放定址法（Open鏈地址法（Separate

索 數(shù)索 數(shù)64單向鏈表8 樹節(jié)點(diǎn)數(shù)量少到一定程度時(shí)，又會(huì)轉(zhuǎn)為單向鏈 先生成key（必須是整數(shù)key跟數(shù)組的大小進(jìn)行相關(guān)運(yùn)算，生成一個(gè)為了提高效率，可以使用&位運(yùn)算取代%運(yùn)算【前提：將數(shù)組的長(zhǎng)度設(shè)計(jì)為2的冪（2n）11001011&&讓哈希值更加均勻分布→減少哈 次數(shù)→提升哈希表的性key在Java中，HashMap的keyhashCode、equalskey10 的二進(jìn)制格式轉(zhuǎn)為整數(shù)>>>和^高32bit32bit32bit111111111111111111111111111111111011011000111001011011111100value>>>000000000000000000000000000000001111111111111111111111111111value^(value>>>11111111111111111111111111111111010010011100011010010000001154895?103+4?102+8?101+9?比如字符串jack，由j、a、c、 因此，jackj?n3+a?n2+c?n1+k?n0，等價(jià)于[(j?n+a)?n+c]?n+在JDKn為3131JVM31*i(i5)–31*i=(2^5–1)*i=i*2^5–i=(i<<5)–31不僅僅是符合2^n1，它是個(gè)奇素?cái)?shù)（既是奇數(shù)，又是素?cái)?shù)，也就是質(zhì)數(shù)

keyhashCode、equalsequals2keynullx，x.equals(x)必須返回nullx、yy.equals(xtrue，x.equals(ynullx、y、zx.equals(y)、y.equals(ztrue，那么x.equals(znullx、yequalsx.equals(ytruenullx，x.equals(nullhashCodeequalstrue2keyhashCodekeyequals不重寫hashCode方法只重寫equals會(huì)有什 2equalstruekey裝填因子（LoadFactor）：TreeMapvs元素具備可比較性且要求升序遍歷（按照元素從小到大 索索 數(shù) nodeLinkedHashMapnode索 數(shù)LinkedHashMap10%8=20%8=30%8