hashMap的數據結構

null1145 發布于2019-08-16 10:32 / 1042人閱讀

摘要：也就是說，紅黑樹是一種相對平衡的查找二叉樹，這使他不僅便于查找，也便于插入和刪除，這對于既需要插入也需要查找的是非常有利的下一節數據哈希值的計算和在中的存儲位置

在jdk8中，HashMap是用了數組和鏈表以及紅黑樹這三種數據結構

首先，在hashmap類中，都有一個table數組，我們在存儲數據時，對這個數據的hash值進行一系列的計算計算出它在Table中的位置(下標)，并將它存放進去
然而，我們在hashmap是什么 中提到，不同的對象的Hash值可能相同，那么相同的Hash值會導致不同的數據在數組中有相同的存儲位置，我們雖然創造了一系列的解決辦法，但并不能完全的避免這種沖突，那么，當產生沖突時，hashmap是怎樣解決的呢？
當產生沖突時，如data1和data2 ,我們把data2放在data1后的列表中，這樣就不會因為哈希值的沖突而對數據產生影響。
1.時間復雜度
我們知道，當某條鏈表的長度大于8時，就會將其轉換為紅黑樹。遍歷一條鏈表的時間復雜度O(n),當一條鏈表過長時，遍歷這條鏈表可能會花很長時間，而遍歷一顆紅黑樹的時間復雜度為O（logn）,從而減少了插入或查找的時間
2.紅黑樹
簡單總結下紅黑樹是什么：一種二叉查找樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是Red或Black。通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的。

也就是說，紅黑樹是一種相對平衡的查找二叉樹，這使他不僅便于查找，也便于插入和刪除，這對于既需要插入也需要查找的HashMap是非常有利的

下一節：數據哈希值的計算和在table中的存儲位置

GPU云服務器云服務器 hashmap的工作原理 hashmap存儲結構 HashMap _HashMap

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69986.html

HashMap源碼分析(一):JDK源碼分析系列

摘要：當一個值中要存儲到的時候會根據的值來計算出他的，通過哈希來確認到數組的位置，如果發生哈希碰撞就以鏈表的形式存儲在源碼分析中解釋過，但是這樣如果鏈表過長來的話，會把這個鏈表轉換成紅黑樹來存儲。正文開始注:JDK版本為1.8 HashMap1.8和1.8之前的源碼差別很大目錄簡介數據結構類結構屬性構造方法增加刪除修改總結 1.HashMap簡介 H...

wdzgege 2019-08-16 18:32 評論0 收藏0
hashmap源碼分析

摘要：源碼解析的數據存儲結構中的都是存在數組中的數據節點的數據結構是一個單向的鏈表，，實現了的接口，即實現了，，等這些函數，這些都是基本的讀取修改值的函數。的作用是判斷是否包含的作用是判斷是否包含值為的元素 HashMap源碼解析 hashmap的數結構（1）在Java中，數據結構分為兩種，一種是數組，另一個是模型指針即引用，所有的數據結構都可以用這兩種基本結構所構造，HashMap就是一...

codercao 2019-08-16 12:31 評論0 收藏0
HashMap 源碼詳細分析(JDK1.8)

摘要：則使用了拉鏈式的散列算法，并在中引入了紅黑樹優化過長的鏈表。如果大家對紅黑樹感興趣，可以閱讀我的另一篇文章紅黑樹詳細分析。構造方法構造方法分析的構造方法不多，只有四個。 1.概述本篇文章我們來聊聊大家日常開發中常用的一個集合類 - HashMap。HashMap 最早出現在 JDK 1.2中，底層基于散列算法實現。HashMap 允許 null 鍵和 null 值，在計算哈鍵的哈希值...

monw3c 2019-08-15 13:48 評論0 收藏0
重新詳盡的理解HasMap

摘要：根據的重新計算值。如果這兩個的通過比較返回，新添加的將覆蓋集合中原有的，但不會覆蓋。如果這兩個的通過比較返回，新添加的將與集合中原有形成鏈，而且新添加的位于鏈的頭部具體說明繼續看方法的說明。關于hashCode hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用來在散列存儲結構中確定對象的存儲地址的. 1.hashcode是用來...

maxmin 2019-08-16 15:04 評論0 收藏0
HashMap 你真的了解嗎？

摘要：加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了加載因子與當前容量的乘積時，則要對該哈希表進行操作即重建內部數據結構，從而哈希表將具有大約兩倍的桶數。 showImg(https://upload-images.jianshu.io/upload_images/4565148-98b22ba5ae7d9723.jpg?imageMogr2/auto-...

RdouTyping 2019-08-19 11:33 評論0 收藏0