Repository navigation
Expand file tree
/
Copy pathjava-hashtable-hashmap-treemap.html
More file actions
211 lines (192 loc) · 44.8 KB
/
Copy pathjava-hashtable-hashmap-treemap.html
File metadata and controls
211 lines (192 loc) · 44.8 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0,viewport-fit=cover"><title>对比Hashtable、HashMap、TreeMap有什么不同? | WenQian Dong's Web</title><meta name="author" content="WenQian Dong"><meta name="copyright" content="WenQian Dong"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="Map容器Map 通常被包括在 Java 集合框架中,但是其本身并不是真正的 Collection 集合类型。 Hashtable 、 HashMap 、 TreeMap 都是 Map 的实现,是以键值对的形式存储和操作数据的容器类型。  => {
if (ttl === 0) return
const now = Date.now()
const expiry = now + ttl * 86400000
const item = {
value,
expiry
}
localStorage.setItem(key, JSON.stringify(item))
},
get: key => {
const itemStr = localStorage.getItem(key)
if (!itemStr) {
return undefined
}
const item = JSON.parse(itemStr)
const now = Date.now()
if (now > item.expiry) {
localStorage.removeItem(key)
return undefined
}
return item.value
}
}
win.getScript = (url, attr = {}) => new Promise((resolve, reject) => {
const script = document.createElement('script')
script.src = url
script.async = true
script.onerror = reject
script.onload = script.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
script.onload = script.onreadystatechange = null
resolve()
}
Object.keys(attr).forEach(key => {
script.setAttribute(key, attr[key])
})
document.head.appendChild(script)
})
win.getCSS = (url, id = false) => new Promise((resolve, reject) => {
const link = document.createElement('link')
link.rel = 'stylesheet'
link.href = url
if (id) link.id = id
link.onerror = reject
link.onload = link.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
link.onload = link.onreadystatechange = null
resolve()
}
document.head.appendChild(link)
})
win.activateDarkMode = () => {
document.documentElement.setAttribute('data-theme', 'dark')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
}
}
win.activateLightMode = () => {
document.documentElement.setAttribute('data-theme', 'light')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
}
}
const t = saveToLocal.get('theme')
if (t === 'dark') activateDarkMode()
else if (t === 'light') activateLightMode()
const asideStatus = saveToLocal.get('aside-status')
if (asideStatus !== undefined) {
if (asideStatus === 'hide') {
document.documentElement.classList.add('hide-aside')
} else {
document.documentElement.classList.remove('hide-aside')
}
}
const detectApple = () => {
if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
document.documentElement.classList.add('apple')
}
}
detectApple()
})(window)</script><meta name="generator" content="Hexo 7.1.1"><link rel="alternate" href="/atom.xml" title="WenQian Dong's Web" type="application/atom+xml">
</head><body><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="https://raw.githubusercontent.com/wqdchn/blog-image/master/avatar.jpg" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="sidebar-site-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">45</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">44</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">4</div></a></div><hr class="custom-hr"/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 归档</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/links/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于我</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://raw.githubusercontent.com/wqdchn/blog-image/master/daily_pic2.jpg')"><nav id="nav"><span id="blog-info"><a href="/" title="WenQian Dong's Web"><img class="site-icon" src="https://raw.githubusercontent.com/wqdchn/blog-image/master/avatar.jpg"/><span class="site-name">WenQian Dong's Web</span></a></span><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 归档</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/links/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于我</span></a></div></div><div id="toggle-menu"><a class="site-page" href="javascript:void(0);"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">对比Hashtable、HashMap、TreeMap有什么不同?</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2020-04-01T00:14:00.000Z" title="发表于 2020-04-01 08:14:00">2020-04-01</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2024-02-17T01:39:55.036Z" title="更新于 2024-02-17 09:39:55">2024-02-17</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/Java/">Java</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="对比Hashtable、HashMap、TreeMap有什么不同?"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"><i class="fa-solid fa-spinner fa-spin"></i></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><span id="more"></span>
<h3 id="Map容器"><a href="#Map容器" class="headerlink" title="Map容器"></a>Map容器</h3><p>Map 通常被包括在 Java 集合框架中,但是其本身并不是真正的 Collection 集合类型。 Hashtable 、 HashMap 、 TreeMap 都是 Map 的实现,是以键值对的形式存储和操作数据的容器类型。</p>
<p></p>
<p> Hashtable 继承自 Dictionary 类,而 HashMap 与 TreeMap 继承 AbstractMap 类,它们的类结构上是不同的,不同的实现表明了它们不同的设计目的。</p>
<p> Hashtable 是 Java 类库关于哈希表的一个早期实现,它的方法都使用 synchronized 进行同步,是线程安全的。 Hashtable 不允许 key 为 null ,不允许 value 为 null 。 </p>
<p> HashMap 是使用最广的一种哈希表实现,大部分方法与 Hashtable 是相似的,但是减少了同步开销,因此是线程不安全的。 HashMap 允许 key 为 null ,允许 value 为 null 。</p>
<p> TreeMap 是基于红黑树的一种提供顺序访问的 Map ,与前两者不同,它的 put() 、 get() 等操作的时间复杂度都是 O(log(n)) 。其顺序可以通过 Comparator 来决定,或者根据键值的自然顺序 Comparable 来决定。它也是线程不安全的。 TreeMap 不允许 key 为 null ,允许 value 为 null 。</p>
<p>对于 TreeMap ,当实现 Comparator 接口时,若未对 null 情况进行判断,则可能抛 NullPointerException 异常。如果针对 null 情况实现了特别处理,则可以 put() 存入,但是却不能正常使用 get() 访问,只能通过遍历去访问。</p>
<p>因此,建议遵循设计的规范,不要做这种使用错误。例如 HashMap 明确声明是线程不安全的,如果不加考虑,直接简单地应用在多线程场景中,总是要出问题的。</p>
<h3 id="HashMap的实现"><a href="#HashMap的实现" class="headerlink" title="HashMap的实现"></a>HashMap的实现</h3><p> HashMap 的底层是数组和链表组成的复合结构,数组被分成桶 bucket ,里面存放哈希值,通过哈希值来确定数组寻址时的数组下标。哈希值相同的键值对则以链表的形式存储,如果链表的长度超过阈值 TREEIFY_THRESHOLD = 8 ,则对链表进行改造,转化为红黑树。当红黑树的节点小于阈值 UNTREEIFY_THRESHOLD = 6 时,则对红黑树进行改造,转化为链表。我想这是为了避免链表在阈值附近频繁地转换造成过大的开销而设置的两个临界点。</p>
<h3 id="HashMap的工作流程"><a href="#HashMap的工作流程" class="headerlink" title="HashMap的工作流程"></a>HashMap的工作流程</h3><h4 id="存储对象"><a href="#存储对象" class="headerlink" title="存储对象"></a>存储对象</h4><p>存储对象时,将键值对 K/V 传给 put() 方法:</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> V <span class="title function_">put</span><span class="params">(K key, V value)</span> {</span><br><span class="line"> <span class="keyword">return</span> putVal(hash(key), key, value, <span class="literal">false</span>, <span class="literal">true</span>);</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>然后调用 hash() 方法计算 K 的哈希值:</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="type">int</span> <span class="title function_">hash</span><span class="params">(Object key)</span> {</span><br><span class="line"> <span class="type">int</span> h;</span><br><span class="line"> <span class="keyword">return</span> (key == <span class="literal">null</span>) ? <span class="number">0</span> : (h = key.hashCode()) ^ (h >>> <span class="number">16</span>);</span><br><span class="line">}</span><br><span class="line">``` </span><br><span class="line"></span><br><span class="line">这里进行了一个 hashCode() 高位数据移位到低位 h >>> <span class="number">16</span> 并进行异或运算 ^ 的操作。将高位和低位进行异或运算,只要有高位或低位中有一位的变化,整个 hash() 返回的哈希值就会发生变化,尽可能地减少哈希碰撞。</span><br><span class="line"></span><br><span class="line">在计算得到数组下标之后,通过 putVal() 方法进行存储, putVal() 方法本身的逻辑非常密集,从初始化、扩容、树化都与它有关:</span><br><span class="line"></span><br><span class="line">```Java</span><br><span class="line"><span class="keyword">final</span> V <span class="title function_">putVal</span><span class="params">(<span class="type">int</span> hash, K key, V value, <span class="type">boolean</span> onlyIfAbsent,</span></span><br><span class="line"><span class="params"> <span class="type">boolean</span> evict)</span> {</span><br><span class="line"> Node<K,V>[] tab; Node<K,V> p; <span class="type">int</span> n, i;</span><br><span class="line"> <span class="keyword">if</span> ((tab = table) == <span class="literal">null</span> || (n = tab.length) == <span class="number">0</span>)</span><br><span class="line"> n = (tab = resize()).length;</span><br><span class="line"> <span class="keyword">if</span> ((p = tab[i = (n - <span class="number">1</span>) & hash]) == <span class="literal">null</span>)</span><br><span class="line"> tab[i] = newNode(hash, key, value, <span class="literal">null</span>);</span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> Node<K,V> e; K k;</span><br><span class="line"> <span class="keyword">if</span> (p.hash == hash &&</span><br><span class="line"> ((k = p.key) == key || (key != <span class="literal">null</span> && key.equals(k))))</span><br><span class="line"> e = p;</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span> (p <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line"> e = ((TreeNode<K,V>)p).putTreeVal(<span class="built_in">this</span>, tab, hash, key, value);</span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">binCount</span> <span class="operator">=</span> <span class="number">0</span>; ; ++binCount) {</span><br><span class="line"> <span class="keyword">if</span> ((e = p.next) == <span class="literal">null</span>) {</span><br><span class="line"> p.next = newNode(hash, key, value, <span class="literal">null</span>);</span><br><span class="line"> <span class="keyword">if</span> (binCount >= TREEIFY_THRESHOLD - <span class="number">1</span>) <span class="comment">// -1 for 1st</span></span><br><span class="line"> treeifyBin(tab, hash);</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (e.hash == hash &&</span><br><span class="line"> ((k = e.key) == key || (key != <span class="literal">null</span> && key.equals(k))))</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> p = e;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (e != <span class="literal">null</span>) { <span class="comment">// existing mapping for key</span></span><br><span class="line"> <span class="type">V</span> <span class="variable">oldValue</span> <span class="operator">=</span> e.value;</span><br><span class="line"> <span class="keyword">if</span> (!onlyIfAbsent || oldValue == <span class="literal">null</span>)</span><br><span class="line"> e.value = value;</span><br><span class="line"> afterNodeAccess(e);</span><br><span class="line"> <span class="keyword">return</span> oldValue;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> ++modCount;</span><br><span class="line"> <span class="keyword">if</span> (++size > threshold)</span><br><span class="line"> resize();</span><br><span class="line"> afterNodeInsertion(evict);</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>如果哈希表为 null , resize() 方法会负责初始化 tab = resize() 。</p>
<p>当哈希表容量不足时,出现 ++size > threshold , resize() 方法还会进行扩容。默认的初始化容量参数和最大容量参数如下。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * The default initial capacity - MUST be a power of two.</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="type">int</span> <span class="variable">DEFAULT_INITIAL_CAPACITY</span> <span class="operator">=</span> <span class="number">1</span> << <span class="number">4</span>; <span class="comment">// aka 16, 2的4次方</span></span><br><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="type">int</span> <span class="variable">MAXIMUM_CAPACITY</span> <span class="operator">=</span> <span class="number">1</span> << <span class="number">30</span>; <span class="comment">// 2的30次方</span></span><br></pre></td></tr></table></figure>
<p>如果 K 的 hash 值在 HashMap 中不存在,则执行插入,若存在,则发生碰撞。</p>
<p>如果 K 的 hash 值在 HashMap 中存在,且它们两者 equals 返回 true ,则更新键值对。</p>
<p>如果 K 的 hash 值在 HashMap 中存在,且它们两者 equals 返回 false,则插入链表的尾部(尾插法)或者红黑树中(树的添加方式)。</p>
<h4 id="获取对象"><a href="#获取对象" class="headerlink" title="获取对象"></a>获取对象</h4><p>获取对象时,将 K 传给 get() 方法:</p>
<p>调用 hash(K) 方法,计算 K 的 hash 值,从而获取该键值所在链表的数组下标。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> V <span class="title function_">get</span><span class="params">(Object key)</span> {</span><br><span class="line"> Node<K,V> e;</span><br><span class="line"> <span class="keyword">return</span> (e = getNode(hash(key), key)) == <span class="literal">null</span> ? <span class="literal">null</span> : e.value;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>然后顺序遍历链表,根据equals()方法查找相同 Node 链表中 K 值对应的 V 值。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">final</span> Node<K,V> <span class="title function_">getNode</span><span class="params">(<span class="type">int</span> hash, Object key)</span> {</span><br><span class="line"> Node<K,V>[] tab; Node<K,V> first, e; <span class="type">int</span> n; K k;</span><br><span class="line"> <span class="keyword">if</span> ((tab = table) != <span class="literal">null</span> && (n = tab.length) > <span class="number">0</span> &&</span><br><span class="line"> (first = tab[(n - <span class="number">1</span>) & hash]) != <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">if</span> (first.hash == hash && <span class="comment">// always check first node</span></span><br><span class="line"> ((k = first.key) == key || (key != <span class="literal">null</span> && key.equals(k))))</span><br><span class="line"> <span class="keyword">return</span> first;</span><br><span class="line"> <span class="keyword">if</span> ((e = first.next) != <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">if</span> (first <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line"> <span class="keyword">return</span> ((TreeNode<K,V>)first).getTreeNode(hash, key);</span><br><span class="line"> <span class="keyword">do</span> {</span><br><span class="line"> <span class="keyword">if</span> (e.hash == hash &&</span><br><span class="line"> ((k = e.key) == key || (key != <span class="literal">null</span> && key.equals(k))))</span><br><span class="line"> <span class="keyword">return</span> e;</span><br><span class="line"> } <span class="keyword">while</span> ((e = e.next) != <span class="literal">null</span>);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h4 id="扩容"><a href="#扩容" class="headerlink" title="扩容"></a>扩容</h4><p>扩容的方法比较复杂</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"></span><br><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="type">float</span> <span class="variable">DEFAULT_LOAD_FACTOR</span> <span class="operator">=</span> <span class="number">0.75f</span>; <span class="comment">// 负载因子</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">final</span> Node<K,V>[] resize() {</span><br><span class="line"> <span class="comment">// ...</span></span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span> ((newCap = oldCap << <span class="number">1</span>) < MAXIMUM_CAPACIY &&</span><br><span class="line"> oldCap >= DEFAULT_INITIAL_CAPAITY)</span><br><span class="line"> newThr = oldThr << <span class="number">1</span>; <span class="comment">// double there</span></span><br><span class="line"> <span class="comment">// ... </span></span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span> (oldThr > <span class="number">0</span>) <span class="comment">// initial capacity was placed in threshold</span></span><br><span class="line"> newCap = oldThr;</span><br><span class="line"> <span class="keyword">else</span> { </span><br><span class="line"> <span class="comment">// zero initial threshold signifies using defaultsfults</span></span><br><span class="line"> newCap = DEFAULT_INITIAL_CAPAITY;</span><br><span class="line"> newThr = (<span class="type">int</span>)(DEFAULT_LOAD_ATOR* DEFAULT_INITIAL_CAPACITY;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (newThr ==<span class="number">0</span>) {</span><br><span class="line"> <span class="type">float</span> <span class="variable">ft</span> <span class="operator">=</span> (<span class="type">float</span>)newCap * loadFator;</span><br><span class="line"> newThr = (newCap < MAXIMUM_CAPACITY && ft < (<span class="type">float</span>)MAXIMUM_CAPACITY ?(<span class="type">int</span>)ft : Integer.MAX_VALUE);</span><br><span class="line"> }</span><br><span class="line"> threshold = neThr;</span><br><span class="line"> Node<K,V>[] newTab = (Node<K,V>[])<span class="keyword">new</span> <span class="title class_">Node</span>[newap];</span><br><span class="line"> table = n;</span><br><span class="line"> <span class="comment">// 移动到新的数组结构e数组结构 </span></span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<p>如果负载因子 * 容量 > 元素数量,则会进行扩容。扩容时创建一个新的数组,其容量为旧数组的两倍,并重新计算旧数组中结点的存储位置。结点在新数组中的位置只有两种,原下标位置或原下标+旧数组的大小。</p>
<h4 id="树化改造"><a href="#树化改造" class="headerlink" title="树化改造"></a>树化改造</h4><p>在使用 put() 方法进行存储对象时,除了会遇到扩容方法,还有可能遇到树化改造:</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"></span><br><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="type">int</span> <span class="variable">MIN_TREEIFY_CAPACITY</span> <span class="operator">=</span> <span class="number">64</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">final</span> <span class="keyword">void</span> <span class="title function_">treeifyBin</span><span class="params">(Node<K,V>[] tab, <span class="type">int</span> hash)</span> {</span><br><span class="line"> <span class="type">int</span> n, index; Node<K,V> e;</span><br><span class="line"> <span class="keyword">if</span> (tab == <span class="literal">null</span> || (n = tab.length) < MIN_TREEIFY_CAPACITY)</span><br><span class="line"> resize();</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span> ((e = tab[index = (n - <span class="number">1</span>) & hash]) != <span class="literal">null</span>) {</span><br><span class="line"> TreeNode<K,V> hd = <span class="literal">null</span>, tl = <span class="literal">null</span>;</span><br><span class="line"> <span class="keyword">do</span> {</span><br><span class="line"> TreeNode<K,V> p = replacementTreeNode(e, <span class="literal">null</span>);</span><br><span class="line"> <span class="keyword">if</span> (tl == <span class="literal">null</span>)</span><br><span class="line"> hd = p;</span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> p.prev = tl;</span><br><span class="line"> tl.next = p;</span><br><span class="line"> }</span><br><span class="line"> tl = p;</span><br><span class="line"> } <span class="keyword">while</span> ((e = e.next) != <span class="literal">null</span>);</span><br><span class="line"> <span class="keyword">if</span> ((tab[index] = hd) != <span class="literal">null</span>)</span><br><span class="line"> hd.treeify(tab);</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>如果容量小于 MIN_TREEIFY_CAPACITY,只会进行简单的扩容。</p>
<p>如果容量大于 MIN_TREEIFY_CAPACITY ,则会进行树化改造。</p>
<p>HashMap 之所以要进行树化改造,是因为底层结构中链表的遍历时间复杂度是 O(N) 的,在哈希碰撞较为严重的时候,链表较长,其存取性能较低,还可能有额外的安全隐患。</p>
<h3 id="hashCode"><a href="#hashCode" class="headerlink" title="hashCode"></a>hashCode</h3><p>hashCode 是所有 Java 对象的固有方法,如果不重载的话,返回的实际上是该对象在 JVM 的堆上内存地址,而不同对象的内存地址肯定不同,所以这个 hashCode 也就肯定不同了。如果重载了的话,由于采用的算法的问题,有可能导致两个不同对象的hashCode相同。</p>
<h3 id="equals-的特性。"><a href="#equals-的特性。" class="headerlink" title="equals 的特性。"></a>equals 的特性。</h3><p>自反性:对于任何非空引用值 x,x.equals(x) 都应返回 true。<br>对称性:对于任何非空引用值 x 和 y,当且仅当 y.equals(x) 返回 true 时,x.equals(y) 才应返回 true。<br>传递性:对于任何非空引用值 x、y 和 z,如果 x.equals(y) 返回 true,并且 y.equals(z) 返回 true,那么 x.equals(z) 应返回 true。<br>一致性:对于任何非空引用值 x 和 y,多次调用 x.equals(y) 始终返回 true 或始终返回 false,前提是对象上 equals 比较中所用的信息没有被修改。<br>非空性:对于任何非空引用值 x,x.equals(null) 都应返回 false。</p>
<h3 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h3><p>大部分使用 Map 的场景,通常就是放入、访问或者删除,而对顺序没有特别要求,HashMap 在这种情况下基本是最好的选择。HashMap 的性能表现非常依赖于哈希码的有效性,请务必遵守 hashCode 和 equals 的一些基本约定:</p>
<ul>
<li>equals 相等,hashCode 一定要相等。</li>
<li>重写了 hashCode 也要重写 equals。</li>
<li>hashCode 需要保持一致性,状态改变返回的哈希值仍然要一致。</li>
</ul>
<p>以上内容都基于 jdk1.8.0_161 。</p>
<h3 id="参考资料"><a href="#参考资料" class="headerlink" title="参考资料"></a>参考资料</h3><p><a href="https://mp.weixin.qq.com/s?__biz=MzI3NzE0NjcwMg==&mid=2650125459&idx=1&sn=56a14e497b5644eba72f034ac791a4d9&chksm=f36ba9b2c41c20a43611ef0d54747abdaf12f1f867ab23f2f0fc8eac87c657353c734f926cbb&scene=21#wechat_redirect">为啥 HashMap 的默认容量是16?</a><br><a href="https://mp.weixin.qq.com/s?__biz=MjM5NzMyMjAwMA==&mid=2651486554&idx=1&sn=23a0786a8c401c799042ac7a9aa0e811&chksm=bd2515258a529c3312285c2536a92a7eb56805ded2eb726b72ab06beabe8e167d00d20789333&scene=126&sessionid=1585703424&key=e7b22394d9386bca990226e723bf6055c836e7d8b7dabe02034009cb225b77c844a21b5027ec82bfa738aa258fea0d41ca89603c0b8e93de1540103a2ec25a970c5c796cb2d499aaa6fce20c5e2772c3&ascene=1&uin=MTIzMjgzNDMyNw==&devicetype=Windows+10&version=62080079&lang=zh_CN&exportkey=AxuN6zS95LSdyZL9KQG5Oj0=&pass_ticket=LGstMxzdbnh6CyV6rurD3W6ylR1d9GRkDMmoMP80xAWiS91bl+2xlMkQ2wePQ23q">我说我了解集合类,面试官竟然问我为啥 HashMap 的负载因子不设置成1!?</a></p>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta"><i class="fas fa-circle-user fa-fw"></i>文章作者: </span><span class="post-copyright-info"><a href="https://wqdchn.github.io">WenQian Dong</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta"><i class="fas fa-square-arrow-up-right fa-fw"></i>文章链接: </span><span class="post-copyright-info"><a href="https://wqdchn.github.io/java-hashtable-hashmap-treemap.html">https://wqdchn.github.io/java-hashtable-hashmap-treemap.html</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta"><i class="fas fa-circle-exclamation fa-fw"></i>版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外,均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://wqdchn.github.io" target="_blank">WenQian Dong's Web</a>!</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/Java/">Java</a><a class="post-meta__tags" href="/tags/%E5%AE%B9%E5%99%A8/">容器</a><a class="post-meta__tags" href="/tags/%E9%9B%86%E5%90%88/">集合</a><a class="post-meta__tags" href="/tags/%E5%93%88%E5%B8%8C%E8%A1%A8/">哈希表</a></div><div class="post_share"><div class="social-share" data-image="https://raw.githubusercontent.com/wqdchn/blog-image/master/avatar.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1.1.3/sharejs/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1.1.3/sharejs/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/java-basic-polymorphism.html" title="Java基础:多态"><div class="cover" style="background: var(--default-bg-color)"></div><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">Java基础:多态</div></div></a></div><div class="next-post pull-right"><a href="/java-vector-arraylist-linkedlist.html" title="对比Vector、ArrayList、LinkedList有何区别?"><div class="cover" style="background: var(--default-bg-color)"></div><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">对比Vector、ArrayList、LinkedList有何区别?</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>相关推荐</span></div><div class="relatedPosts-list"><div><a href="/java-vector-arraylist-linkedlist.html" title="对比Vector、ArrayList、LinkedList有何区别?"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2020-03-31</div><div class="title">对比Vector、ArrayList、LinkedList有何区别?</div></div></a></div><div><a href="/java-basic-polymorphism.html" title="Java基础:多态"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2020-04-10</div><div class="title">Java基础:多态</div></div></a></div><div><a href="/java-basic-classloader.html" title="Java基础:类加载过程"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2020-04-14</div><div class="title">Java基础:类加载过程</div></div></a></div><div><a href="/leetcode-three-sum.html" title="LeetCode第15题Three Sum"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2019-09-18</div><div class="title">LeetCode第15题Three Sum</div></div></a></div><div><a href="/leetcode-two-sum.html" title="LeetCode第1题Two Sum"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2019-09-12</div><div class="title">LeetCode第1题Two Sum</div></div></a></div><div><a href="/leetcode-valid-anagram.html" title="LeetCode第242题Valid Anagram"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2019-09-29</div><div class="title">LeetCode第242题Valid Anagram</div></div></a></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="https://raw.githubusercontent.com/wqdchn/blog-image/master/avatar.jpg" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">WenQian Dong</div><div class="author-info__description">技术,杂谈,三国厨,历史向,Google粉</div></div><div class="card-info-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">45</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">44</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">4</div></a></div><a id="card-info-btn" href="https://github.com/wqdchn"><i class="fab fa-github"></i><span>Follow Me</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://github.com/wqdchn" target="_blank" title="Github"><i class="fab fa-github" style="color: #24292e;"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>公告</span></div><div class="announcement_content">This is my Blog</div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-3"><a class="toc-link" href="#Map%E5%AE%B9%E5%99%A8"><span class="toc-number">1.</span> <span class="toc-text">Map容器</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#HashMap%E7%9A%84%E5%AE%9E%E7%8E%B0"><span class="toc-number">2.</span> <span class="toc-text">HashMap的实现</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#HashMap%E7%9A%84%E5%B7%A5%E4%BD%9C%E6%B5%81%E7%A8%8B"><span class="toc-number">3.</span> <span class="toc-text">HashMap的工作流程</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%AD%98%E5%82%A8%E5%AF%B9%E8%B1%A1"><span class="toc-number">3.1.</span> <span class="toc-text">存储对象</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E8%8E%B7%E5%8F%96%E5%AF%B9%E8%B1%A1"><span class="toc-number">3.2.</span> <span class="toc-text">获取对象</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%89%A9%E5%AE%B9"><span class="toc-number">3.3.</span> <span class="toc-text">扩容</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%A0%91%E5%8C%96%E6%94%B9%E9%80%A0"><span class="toc-number">3.4.</span> <span class="toc-text">树化改造</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#hashCode"><span class="toc-number">4.</span> <span class="toc-text">hashCode</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#equals-%E7%9A%84%E7%89%B9%E6%80%A7%E3%80%82"><span class="toc-number">5.</span> <span class="toc-text">equals 的特性。</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%80%BB%E7%BB%93"><span class="toc-number">6.</span> <span class="toc-text">总结</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E8%B5%84%E6%96%99"><span class="toc-number">7.</span> <span class="toc-text">参考资料</span></a></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/reply-2021.html" title="请回答 2021">请回答 2021</a><time datetime="2022-01-03T04:46:59.000Z" title="发表于 2022-01-03 12:46:59">2022-01-03</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/aloha-heja-he.html" title="Aloha Heja He">Aloha Heja He</a><time datetime="2020-08-09T13:18:30.000Z" title="发表于 2020-08-09 21:18:30">2020-08-09</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/how-is-going-2020-08-01.html" title="庚子年·仲夏记事">庚子年·仲夏记事</a><time datetime="2020-08-01T15:01:57.000Z" title="发表于 2020-08-01 23:01:57">2020-08-01</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/how-is-going-2020-06-30.html" title="庚子年·夏至记事">庚子年·夏至记事</a><time datetime="2020-06-30T11:26:57.000Z" title="发表于 2020-06-30 19:26:57">2020-06-30</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/how-is-going-2020-05-31.html" title="庚子年·初夏记事">庚子年·初夏记事</a><time datetime="2020-05-31T01:45:44.000Z" title="发表于 2020-05-31 09:45:44">2020-05-31</time></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">©2017 - 2024 By WenQian Dong</div><div class="framework-info"><span>框架 </span><a href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside-config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><span class="scroll-percent"></span><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js?v=4.12.0"></script><script src="/js/main.js?v=4.12.0"></script><script src="https://cdn.jsdelivr.net/npm/@fancyapps/ui@5.0.32/dist/fancybox/fancybox.umd.min.js"></script><div class="js-pjax"></div><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>