資訊專欄INFORMATION COLUMN
摘要：也就是說，紅黑樹是一種相對(duì)平衡的查找二叉樹，這使他不僅便于查找，也便于插入和刪除，這對(duì)于既需要插入也需要查找的是非常有利的下一節(jié)數(shù)據(jù)哈希值的計(jì)算和在中的存儲(chǔ)位置
在jdk8中，HashMap是用了數(shù)組和鏈表以及紅黑樹這三種數(shù)據(jù)結(jié)構(gòu)
首先，在hashmap類中，都有一個(gè)table數(shù)組，我們?cè)诖鎯?chǔ)數(shù)據(jù)時(shí)，對(duì)這個(gè)數(shù)據(jù)的hash值進(jìn)行一系列的計(jì)算 計(jì)算出它在Table中的位置(下標(biāo))，并將它存放進(jìn)去
然而，我們在hashmap是什么 中提到，不同的對(duì)象的Hash值可能相同，那么相同的Hash值會(huì)導(dǎo)致不同的數(shù)據(jù)在數(shù)組中有相同的存儲(chǔ)位置，我們雖然創(chuàng)造了一系列的解決辦法，但并不能完全的避免這種沖突，那么，當(dāng)產(chǎn)生沖突時(shí)，hashmap是怎樣解決的呢？
當(dāng)產(chǎn)生沖突時(shí)，如data1和data2 ,我們把data2放在data1后的列表中，這樣就不會(huì)因?yàn)楣Ｖ档臎_突而對(duì)數(shù)據(jù)產(chǎn)生影響。
1.時(shí)間復(fù)雜度
我們知道，當(dāng)某條鏈表的長(zhǎng)度大于8時(shí)，就會(huì)將其轉(zhuǎn)換為紅黑樹。遍歷一條鏈表的時(shí)間復(fù)雜度O(n),當(dāng)一條鏈表過長(zhǎng)時(shí)，遍歷這條鏈表可能會(huì)花很長(zhǎng)時(shí)間，而遍歷一顆紅黑樹的時(shí)間復(fù)雜度為O（logn）,從而減少了插入或查找的時(shí)間
2.紅黑樹
簡(jiǎn)單總結(jié)下紅黑樹是什么：一種二叉查找樹，但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是Red或Black。通過對(duì)任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制，紅黑樹確保沒有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍，因而是接近平衡的。
也就是說，紅黑樹是一種相對(duì)平衡的查找二叉樹，這使他不僅便于查找，也便于插入和刪除，這對(duì)于既需要插入也需要查找的HashMap是非常有利的
下一節(jié)：數(shù)據(jù)哈希值的計(jì)算和在table中的存儲(chǔ)位置
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/69986.html
摘要：當(dāng)一個(gè)值中要存儲(chǔ)到的時(shí)候會(huì)根據(jù)的值來計(jì)算出他的，通過哈希來確認(rèn)到數(shù)組的位置，如果發(fā)生哈希碰撞就以鏈表的形式存儲(chǔ)在源碼分析中解釋過，但是這樣如果鏈表過長(zhǎng)來的話，會(huì)把這個(gè)鏈表轉(zhuǎn)換成紅黑樹來存儲(chǔ)。 正文開始 注:JDK版本為1.8 HashMap1.8和1.8之前的源碼差別很大 目錄 簡(jiǎn)介 數(shù)據(jù)結(jié)構(gòu) 類結(jié)構(gòu) 屬性 構(gòu)造方法 增加 刪除 修改 總結(jié) 1.HashMap簡(jiǎn)介 H...
摘要：源碼解析的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)中的都是存在數(shù)組中的數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)是一個(gè)單向的鏈表，，實(shí)現(xiàn)了的接口，即實(shí)現(xiàn)了，，等這些函數(shù)，這些都是基本的讀取修改值的函數(shù)。的作用是判斷是否包含的作用是判斷是否包含值為的元素 HashMap源碼解析 hashmap的數(shù)結(jié)構(gòu) （1）在Java中，數(shù)據(jù)結(jié)構(gòu)分為兩種，一種是數(shù)組，另一個(gè)是模型指針即引用，所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩種基本結(jié)構(gòu)所構(gòu)造，HashMap就是一...
摘要：則使用了拉鏈?zhǔn)降纳⒘兴惴?，并在中引入了紅黑樹優(yōu)化過長(zhǎng)的鏈表。如果大家對(duì)紅黑樹感興趣，可以閱讀我的另一篇文章紅黑樹詳細(xì)分析。構(gòu)造方法構(gòu)造方法分析的構(gòu)造方法不多，只有四個(gè)。 1.概述 本篇文章我們來聊聊大家日常開發(fā)中常用的一個(gè)集合類 - HashMap。HashMap 最早出現(xiàn)在 JDK 1.2中，底層基于散列算法實(shí)現(xiàn)。HashMap 允許 null 鍵和 null 值，在計(jì)算哈鍵的哈希值...
摘要：根據(jù)的重新計(jì)算值。如果這兩個(gè)的通過比較返回，新添加的將覆蓋集合中原有的，但不會(huì)覆蓋。如果這兩個(gè)的通過比較返回，新添加的將與集合中原有形成鏈，而且新添加的位于鏈的頭部具體說明繼續(xù)看方法的說明。 關(guān)于hashCode hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用來在散列存儲(chǔ)結(jié)構(gòu)中確定對(duì)象的存儲(chǔ)地址的. 1.hashcode是用來...
摘要：加載因子是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度。當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時(shí)，則要對(duì)該哈希表進(jìn)行操作即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)，從而哈希表將具有大約兩倍的桶數(shù)。 showImg(https://upload-images.jianshu.io/upload_images/4565148-98b22ba5ae7d9723.jpg?imageMogr2/auto-...
閱讀 3604·2023-04-25 15:52
閱讀 643·2021-11-19 09:40
閱讀 2835·2021-09-26 09:47
閱讀 1088·2021-09-22 15:17
閱讀 3665·2021-08-13 13:25
閱讀 2382·2019-08-30 15:56
閱讀 3549·2019-08-30 13:56
閱讀 2184·2019-08-30 11:27
