-
Notifications
You must be signed in to change notification settings - Fork 19
/
Copy pathHashTable源码解析.html
1 lines (1 loc) · 47.3 KB
/
HashTable源码解析.html
1
<!-- build time:Wed Mar 09 2022 10:17:45 GMT+0800 (GMT+08:00) --><!doctype html><html class="theme-next mist" lang="zh-Hans"><head><meta name="generator" content="Hexo 3.8.0"><meta name="google-site-verification" content="7Tau9WyVgxnsEY9oYedu9g0U6_8akOX3wiKbaYcrg9A"><meta name="baidu-site-verification" content="EVwLiaxdxX"><link href="/css/xps13.css" rel="stylesheet" type="text/css"><link href="/css/message.css" rel="stylesheet" type="text/css"><link href="//fonts.googleapis.com/css?family=Baloo+Bhaijaan|Inconsolata|Josefin+Sans|Montserrat" rel="stylesheet"><script type="text/javascript" src="/js/jquery-1.11.3.min.js"></script><meta charset="UTF-8"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=1"><meta http-equiv="Cache-Control" content="no-transform"><meta http-equiv="Cache-Control" content="no-siteapp"><link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css"><link href="/css/main.css?v=5.1.1" rel="stylesheet" type="text/css"><meta name="keywords" content="Java,"><link rel="alternate" href="/atom.xml" title="MrBird" type="application/atom+xml"><link rel="shortcut icon" type="image/x-icon" href="/bird.png?v=5.1.1"><meta name="description" content="HashTable是Map接口线程安全实现版本，数据结构和方法实现与HashMap类似，本文记录HashTable源码解析，基于JDK1.8。"><meta name="keywords" content="Java"><meta property="og:type" content="article"><meta property="og:title" content="HashTable源码解析"><meta property="og:url" content="http://mrbird.cc/HashTable源码解析.html"><meta property="og:site_name" content="MrBird"><meta property="og:description" content="HashTable是Map接口线程安全实现版本，数据结构和方法实现与HashMap类似，本文记录HashTable源码解析，基于JDK1.8。"><meta property="og:locale" content="zh-Hans"><meta property="og:image" content="http://mrbird.cc/img/QQ20210224-141934@2x.png"><meta property="og:updated_time" content="2021-02-25T03:16:52.783Z"><meta name="twitter:card" content="summary"><meta name="twitter:title" content="HashTable源码解析"><meta name="twitter:description" content="HashTable是Map接口线程安全实现版本，数据结构和方法实现与HashMap类似，本文记录HashTable源码解析，基于JDK1.8。"><meta name="twitter:image" content="http://mrbird.cc/img/QQ20210224-141934@2x.png"><script type="text/javascript" id="hexo.configurations">var NexT=window.NexT||{},CONFIG={root:"/",scheme:"Mist",sidebar:{position:"left",display:"always",offset:12,offset_float:0,b2t:!1,scrollpercent:!0},fancybox:!1,motion:!1}</script><title>HashTable源码解析 | MrBird</title></head><body ondragstart="return!1" class="animsition" lang="zh-Hans" style="overflow-x:hidden;padding-left:280px"><script type="text/javascript" src="/js/mo.min.js"></script><style>body{text-rendering:geometricPrecision!important;font-family:'Josefin Sans','PingFang SC'!important;-webkit-font-smoothing:antialiased!important;-webkit-text-size-adjust:100%!important;background-color:#f4f6f7}@media (min-width:768px) and (max-width:991px){body .header-innerr{width:700px!important}}.header-innerr{margin:0 auto;padding:100px 0 70px;width:880px}@media (min-width:1600px){.container .header-innerr{width:996px}}.header-innerr{position:relative}.header-innerr{padding:0}.header-innerr:after,.header-innerr:before{content:" ";display:table}.header-innerr:after{clear:both}@media (max-width:767px){.header-innerr{width:auto;padding:10px;margin-bottom:-20px}}</style><div class="container sidebar-position-left page-post-detail"><div class="headband"></div><header id="header" class="header"><div class="header-inner"><div class="site-brand-wrapper"><div class="site-meta"><link href="https://fonts.font.im/css?family=Merienda" rel="stylesheet"><div class="custom-logo-site-title"></div><h1 class="site-subtitle" itemprop="description"></h1></div><div class="site-nav-toggle"><button><span class="btn-bar"></span> <span class="btn-bar"></span> <span class="btn-bar"></span></button></div></div><nav class="site-nav"><div class="site-search"><div class="popup search-popup local-search-popup"><div class="local-search-header clearfix"><span class="search-icon"><i class="fa fa-search"></i> </span><span class="popup-btn-close"><i class="fa fa-times-circle"></i></span><div class="local-search-input-wrapper"><input autocomplete="off" placeholder="Search" spellcheck="false" type="text" id="local-search-input"></div></div><div id="local-search-result"></div></div></div></nav></div><div class="header-innerr"></div></header><main id="main" class="main"><div class="main-inner"><div class="content-wrap"><div id="content" class="content"><div id="posts" class="posts-expand"><article class="post post-type-normal" itemscope itemtype="http://schema.org/Article"><link itemprop="mainEntityOfPage" href="http://mrbird.cc/HashTable源码解析.html"><span hidden itemprop="author" itemscope itemtype="http://schema.org/Person"><meta itemprop="name" content="MrBird"><meta itemprop="description" content=""><meta itemprop="image" content="/images/blogImage.jpg"></span><span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization"><meta itemprop="name" content="MrBird"></span><header class="post-header"><h2 class="post-title" itemprop="name headline">HashTable源码解析</h2><div class="post-meta"><span class="post-time"><span class="post-meta-item-icon"><i class="fa fa-calendar-o"></i> </span><span class="post-meta-item-text"></span> <time title="创建于" itemprop="dateCreated datePublished" datetime="2020-08-27T11:25:38+08:00">2020-08-27 </time></span><span></span> <span class="post-meta-divider">|</span> <span class="page-pv"><i class="fa fa-laptop"></i> Visit count <span class="busuanzi-value" id="busuanzi_value_page_pv"></span></span></div></header><div class="post-body" itemprop="articleBody"><p>HashTable是Map接口线程安全实现版本，数据结构和方法实现与HashMap类似，本文记录HashTable源码解析，基于JDK1.8。<a id="more"></a></p><h2 id="类结构"><a href="#类结构" class="headerlink" title="类结构"></a>类结构</h2><p>HashTable类层级关系图： <img src="img/QQ20210224-141934@2x.png" alt="QQ20210224-141934@2x"></p><p>主要成员变量：</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 内部采用Entry数组存储键值对数据，Entry实际为单向链表的表头</span></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">transient</span> Entry<?,?>[] table;</span><br><span class="line"><span class="comment">// HashTable里键值对个数</span></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">transient</span> <span class="keyword">int</span> count;</span><br><span class="line"><span class="comment">// 扩容阈值，当超过这个值时，进行扩容操作，计算方式为：数组容量*加载因子</span></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">int</span> threshold;</span><br><span class="line"><span class="comment">// 加载因子</span></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">float</span> loadFactor;</span><br><span class="line"><span class="comment">// 用于快速失败</span></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">transient</span> <span class="keyword">int</span> modCount = <span class="number">0</span>;</span><br></pre></td></tr></table></figure><p></p><p>table属性通过transient修饰，原因在介绍<a href="/Java-HashMap底层实现原理.html">HashMap源码</a>的时候分析过。</p><p>Entry代码如下：</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">Entry</span><<span class="title">K</span>,<span class="title">V</span>> <span class="keyword">implements</span> <span class="title">Map</span>.<span class="title">Entry</span><<span class="title">K</span>,<span class="title">V</span>> </span>{</span><br><span class="line"> <span class="keyword">final</span> <span class="keyword">int</span> hash;</span><br><span class="line"> <span class="keyword">final</span> K key;</span><br><span class="line"> V value;</span><br><span class="line"> Entry<K,V> next;</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">protected</span> <span class="title">Entry</span><span class="params">(<span class="keyword">int</span> hash, K key, V value, Entry<K,V> next)</span> </span>{</span><br><span class="line"> <span class="keyword">this</span>.hash = hash;</span><br><span class="line"> <span class="keyword">this</span>.key = key;</span><br><span class="line"> <span class="keyword">this</span>.value = value;</span><br><span class="line"> <span class="keyword">this</span>.next = next;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> ......</span><br><span class="line">}</span><br></pre></td></tr></table></figure><p></p><p>Entry为单向链表节点，HashTable采用数组加链表的方式存储数据，不过没有类似于HashMap中当链表过长时转换为红黑树的操作。</p><h2 id="方法解析"><a href="#方法解析" class="headerlink" title="方法解析"></a>方法解析</h2><h3 id="构造函数"><a href="#构造函数" class="headerlink" title="构造函数"></a>构造函数</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 设置指定容量和加载因子，初始化HashTable</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="title">Hashtable</span><span class="params">(<span class="keyword">int</span> initialCapacity, <span class="keyword">float</span> loadFactor)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (initialCapacity < <span class="number">0</span>)</span><br><span class="line"> <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">"Illegal Capacity: "</span>+</span><br><span class="line"> initialCapacity);</span><br><span class="line"> <span class="keyword">if</span> (loadFactor <= <span class="number">0</span> || Float.isNaN(loadFactor))</span><br><span class="line"> <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">"Illegal Load: "</span>+loadFactor);</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> (initialCapacity==<span class="number">0</span>)</span><br><span class="line"> <span class="comment">// 容量最小为1</span></span><br><span class="line"> initialCapacity = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">this</span>.loadFactor = loadFactor;</span><br><span class="line"> table = <span class="keyword">new</span> Entry<?,?>[initialCapacity];</span><br><span class="line"> <span class="comment">// 初始扩容阈值</span></span><br><span class="line"> threshold = (<span class="keyword">int</span>)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + <span class="number">1</span>);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">// 设置指定容量初始HashTable，加载因子为0.75</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="title">Hashtable</span><span class="params">(<span class="keyword">int</span> initialCapacity)</span> </span>{</span><br><span class="line"> <span class="keyword">this</span>(initialCapacity, <span class="number">0.75f</span>);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">// 手动指定数组初始容量为11，加载因子为0.75</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="title">Hashtable</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">this</span>(<span class="number">11</span>, <span class="number">0.75f</span>);</span><br><span class="line">}</span><br></pre></td></tr></table></figure><h3 id="put-K-key-V-value"><a href="#put-K-key-V-value" class="headerlink" title="put(K key, V value)"></a>put(K key, V value)</h3><p><code>put(K key, V value)</code>添加指定键值对，键和值都不能为null：</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 方法synchronized修饰，线程安全</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">synchronized</span> V <span class="title">put</span><span class="params">(K key, V value)</span> </span>{</span><br><span class="line"> <span class="comment">// Make sure the value is not null</span></span><br><span class="line"> <span class="keyword">if</span> (value == <span class="keyword">null</span>) {</span><br><span class="line"> <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// Makes sure the key is not already in the hashtable.</span></span><br><span class="line"> Entry<?,?> tab[] = table;</span><br><span class="line"> <span class="comment">// 得到key的哈希值</span></span><br><span class="line"> <span class="keyword">int</span> hash = key.hashCode();</span><br><span class="line"> <span class="comment">// 得到该key存在到数组中的下标</span></span><br><span class="line"> <span class="keyword">int</span> index = (hash & <span class="number">0x7FFFFFFF</span>) % tab.length;</span><br><span class="line"> <span class="meta">@SuppressWarnings</span>(<span class="string">"unchecked"</span>)</span><br><span class="line"> <span class="comment">// 得到该下标对应的Entry</span></span><br><span class="line"> Entry<K,V> entry = (Entry<K,V>)tab[index];</span><br><span class="line"> <span class="comment">// 如果该下标的Entry不为null，则进行链表遍历</span></span><br><span class="line"> <span class="keyword">for</span>(; entry != <span class="keyword">null</span> ; entry = entry.next) {</span><br><span class="line"> <span class="comment">// 遍历链表，如果存在key相等的节点，则替换这个节点的值，并返回旧值</span></span><br><span class="line"> <span class="keyword">if</span> ((entry.hash == hash) && entry.key.equals(key)) {</span><br><span class="line"> V old = entry.value;</span><br><span class="line"> entry.value = value;</span><br><span class="line"> <span class="keyword">return</span> old;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// 如果数组下标对应的节点为空，或者遍历链表后发现没有和该key相等的节点，则执行插入操作</span></span><br><span class="line"> addEntry(hash, key, value, index);</span><br><span class="line"> <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">addEntry</span><span class="params">(<span class="keyword">int</span> hash, K key, V value, <span class="keyword">int</span> index)</span> </span>{</span><br><span class="line"> <span class="comment">// 模数+1</span></span><br><span class="line"> modCount++;</span><br><span class="line"></span><br><span class="line"> Entry<?,?> tab[] = table;</span><br><span class="line"> <span class="comment">// 判断是否需要扩容</span></span><br><span class="line"> <span class="keyword">if</span> (count >= threshold) {</span><br><span class="line"> <span class="comment">// 如果count大于等于扩容阈值，则进行扩容</span></span><br><span class="line"> rehash();</span><br><span class="line"></span><br><span class="line"> tab = table;</span><br><span class="line"> <span class="comment">// 扩容后，重新计算该key在扩容后table里的下标</span></span><br><span class="line"> hash = key.hashCode();</span><br><span class="line"> index = (hash & <span class="number">0x7FFFFFFF</span>) % tab.length;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="comment">// Creates the new entry.</span></span><br><span class="line"> <span class="meta">@SuppressWarnings</span>(<span class="string">"unchecked"</span>)</span><br><span class="line"> <span class="comment">// 采用头插的方式插入，index位置的节点为新节点的next节点</span></span><br><span class="line"> <span class="comment">// 新节点取代inde位置节点</span></span><br><span class="line"> Entry<K,V> e = (Entry<K,V>) tab[index];</span><br><span class="line"> tab[index] = <span class="keyword">new</span> Entry<>(hash, key, value, e);</span><br><span class="line"> <span class="comment">// count+1</span></span><br><span class="line"> count++;</span><br><span class="line">}</span><br></pre></td></tr></table></figure><p></p><h3 id="rehash"><a href="#rehash" class="headerlink" title="rehash()"></a>rehash()</h3><p><code>rehash</code>扩容操作：</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">protected</span> <span class="keyword">void</span> <span class="title">rehash</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="comment">// 暂存旧的table和容量</span></span><br><span class="line"> <span class="keyword">int</span> oldCapacity = table.length;</span><br><span class="line"> Entry<?,?>[] oldMap = table;</span><br><span class="line"></span><br><span class="line"> <span class="comment">// 新容量为旧容量的2n+1倍</span></span><br><span class="line"> <span class="keyword">int</span> newCapacity = (oldCapacity << <span class="number">1</span>) + <span class="number">1</span>;</span><br><span class="line"> <span class="comment">// 判断新容量是否超过最大容量</span></span><br><span class="line"> <span class="keyword">if</span> (newCapacity - MAX_ARRAY_SIZE > <span class="number">0</span>) {</span><br><span class="line"> <span class="comment">// 如果旧容量已经是最大容量大话，就不扩容了</span></span><br><span class="line"> <span class="keyword">if</span> (oldCapacity == MAX_ARRAY_SIZE)</span><br><span class="line"> <span class="comment">// Keep running with MAX_ARRAY_SIZE buckets</span></span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> <span class="comment">// 新容量最大值只能是MAX_ARRAY_SIZE</span></span><br><span class="line"> newCapacity = MAX_ARRAY_SIZE;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// 用新容量创建一个新Entry数组</span></span><br><span class="line"> Entry<?,?>[] newMap = <span class="keyword">new</span> Entry<?,?>[newCapacity];</span><br><span class="line"> <span class="comment">// 模数+1</span></span><br><span class="line"> modCount++;</span><br><span class="line"> <span class="comment">// 重新计算下次扩容阈值</span></span><br><span class="line"> threshold = (<span class="keyword">int</span>)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + <span class="number">1</span>);</span><br><span class="line"> <span class="comment">// 将新Entry数组赋值给table</span></span><br><span class="line"> table = newMap;</span><br><span class="line"> <span class="comment">// 遍历数组和链表，进行新table赋值操作</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = oldCapacity ; i-- > <span class="number">0</span> ;) {</span><br><span class="line"> <span class="keyword">for</span> (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != <span class="keyword">null</span> ; ) {</span><br><span class="line"> Entry<K,V> e = old;</span><br><span class="line"> old = old.next;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">int</span> index = (e.hash & <span class="number">0x7FFFFFFF</span>) % newCapacity;</span><br><span class="line"> e.next = (Entry<K,V>)newMap[index];</span><br><span class="line"> newMap[index] = e;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure><p></p><h3 id="get-Object-key"><a href="#get-Object-key" class="headerlink" title="get(Object key)"></a>get(Object key)</h3><p><code>get(Object key)</code>获取指定key对应的value：</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">synchronized</span> V <span class="title">get</span><span class="params">(Object key)</span> </span>{</span><br><span class="line"> Entry<?,?> tab[] = table;</span><br><span class="line"> <span class="keyword">int</span> hash = key.hashCode();</span><br><span class="line"> <span class="comment">// 根据key哈希得到index，遍历链表取值</span></span><br><span class="line"> <span class="keyword">int</span> index = (hash & <span class="number">0x7FFFFFFF</span>) % tab.length;</span><br><span class="line"> <span class="keyword">for</span> (Entry<?,?> e = tab[index] ; e != <span class="keyword">null</span> ; e = e.next) {</span><br><span class="line"> <span class="keyword">if</span> ((e.hash == hash) && e.key.equals(key)) {</span><br><span class="line"> <span class="keyword">return</span> (V)e.value;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure><p></p><p>synchronized修饰，线程安全。</p><h3 id="remove-Object-key"><a href="#remove-Object-key" class="headerlink" title="remove(Object key)"></a>remove(Object key)</h3><p><code>remove(Object key)</code>删除指定key，返回对应的value：</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">synchronized</span> V <span class="title">remove</span><span class="params">(Object key)</span> </span>{</span><br><span class="line"> Entry<?,?> tab[] = table;</span><br><span class="line"> <span class="keyword">int</span> hash = key.hashCode();</span><br><span class="line"> <span class="comment">// 获取key对应的index</span></span><br><span class="line"> <span class="keyword">int</span> index = (hash & <span class="number">0x7FFFFFFF</span>) % tab.length;</span><br><span class="line"> <span class="meta">@SuppressWarnings</span>(<span class="string">"unchecked"</span>)</span><br><span class="line"> <span class="comment">// 遍历链表，如果找到key相等的节点，则改变前继和后继节点的关系，并删除相应引用，让GC回收</span></span><br><span class="line"> Entry<K,V> e = (Entry<K,V>)tab[index];</span><br><span class="line"> <span class="keyword">for</span>(Entry<K,V> prev = <span class="keyword">null</span> ; e != <span class="keyword">null</span> ; prev = e, e = e.next) {</span><br><span class="line"> <span class="keyword">if</span> ((e.hash == hash) && e.key.equals(key)) {</span><br><span class="line"> modCount++;</span><br><span class="line"> <span class="keyword">if</span> (prev != <span class="keyword">null</span>) {</span><br><span class="line"> prev.next = e.next;</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> tab[index] = e.next;</span><br><span class="line"> }</span><br><span class="line"> count--;</span><br><span class="line"> V oldValue = e.value;</span><br><span class="line"> e.value = <span class="keyword">null</span>;</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"> <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure><p></p><p>synchronized修饰，线程安全。</p><blockquote><p>剩下方法有兴趣自己阅读源码，public方法都用synchronized修饰，确保线程安全，并发环境下，多线程竞争对象锁，效率低，不推荐使用。线程安全的Map推荐使用ConcurrentHashMap。</p></blockquote><h2 id="和HashMap对比"><a href="#和HashMap对比" class="headerlink" title="和HashMap对比"></a>和HashMap对比</h2><ol><li><p>线程是否安全：HashMap是线程不安全的，HashTable是线程安全的；HashTable内部的方法基本都经过 synchronized修饰；</p></li><li><p>对Null key 和Null value的支持：HashMap中，null可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为null；HashTable中key和value都不能为null，否则抛出空指针异常；</p></li><li><p>初始容量大小和每次扩充容量大小的不同：</p><p>3.1. 创建时如果不指定容量初始值，Hashtable默认的初始大小为11，之后每次扩容，容量变为原来的2n+1。HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍；</p><p>3.2. 创建时如果给定了容量初始值，那么Hashtable会直接使用你给定的大小，而HashMap会将其扩充 为2的幂次方大小。</p></li><li><p>底层数据结构：JDK1.8及以后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间，Hashtable没有这样的机制。</p></li></ol><script>$(".post-body a").not(".thispage").addClass("ignore-href").attr("target","_blank")</script></div><div></div><div><div style="padding:10px 0;margin:20px auto;width:90%;text-align:center;color:#878787" id="reward-div"><div>请作者喝瓶肥宅水🥤</div><button id="rewardButton" style="margin-top:10px" disable="enable" onclick='var e=document.getElementById("QR");"none"===e.style.display?e.style.display="block":e.style.display="none"'><span style="height:46px;width:46px;line-height:46px;border-radius:50%;color:#fe5f55;font-weight:600;background:#ffd5be;border:none;box-shadow:0 4px 8px 0 rgba(255,213,190,.4)">￥</span></button><div id="QR" style="display:none"><div id="wechat" style="display:inline-block"><img id="wechat_qr" src="/img/wechat_pay.png" alt="MrBird WeChat Pay"></div><div id="alipay" style="display:inline-block"><img id="alipay_qr" src="/img/ali_pay.png" alt="MrBird Alipay"></div></div></div><style>#QR img{width:auto;margin:.8em 1em 0 1em}</style></div><div><ul class="post-copyright"><li class="post-copyright-author"><strong>本文作者：</strong> MrBird</li><li class="post-copyright-link"><strong>本文链接：</strong> <a href="http://mrbird.cc/HashTable源码解析.html" title="HashTable源码解析">http://mrbird.cc/HashTable源码解析.html</a></li><li class="post-copyright-license"><strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="external nofollow" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明出处！</li></ul></div><footer class="post-footer"><div class="post-tags" style="margin-bottom:1.3rem"><a href="/tags/Java/" rel="tag"># Java</a></div><div class="post-nav"><div class="post-nav-next post-nav-item"><a href="/CopyOnWriteArraySet源码解析.html" rel="next" title="CopyOnWriteArraySet源码解析"><i class="fa fa-chevron-left"></i> CopyOnWriteArraySet源码解析</a></div><span class="post-nav-divider"></span><div class="post-nav-prev post-nav-item"><a href="/LinkedHashMap源码解析.html" rel="prev" title="LinkedHashMap源码解析">LinkedHashMap源码解析 <i class="fa fa-chevron-right"></i></a></div></div></footer></article><hr><div id="container"></div><div class="post-spread"><div id="comment-div"></div><style>.valine .vlist{margin-bottom:3rem}.valine .vwrap .vcontrol .col.col-60{text-align:left}.valine .vlist .vcard .vhead,.valine .vlist .vcard section .vfooter{text-align:left}.valine .vlist .vcard section{padding-bottom:.5rem!important}.vname{color:#6db33f!important}div#comment-div{margin-bottom:-8rem}.valine .vlist .vcard .vcontent .code,.valine .vlist .vcard .vcontent code,.valine .vlist .vcard .vcontent pre{background:#fbfbfb}.valine .vlist .vcard .vcontent a{color:#6db33f}.valine .vlist .vcard .vimg{border-radius:3px}.valine .vinfo{text-align:left}.valine .vbtn{border-radius:2px;padding:.3rem 1.25rem}.valine .vbtn:active,.valine .vbtn:hover{color:#6db33f;border-color:#6db33f;background-color:#fff}.valine .vwrap .vheader .vinput:focus{border-bottom-color:#6db33f}.valine .vlist .vcard .vcontent.expand:before{background:-webkit-gradient(linear,left top,left bottom,from(hsla(0,0%,100%,0)),to(hsla(0,0%,100%,.2)));background:linear-gradient(180deg,hsla(0,0%,100%,0),hsla(0,0%,100%,.2))}.valine .vlist .vcard .vcontent.expand:after{content:"点击展开";font-size:.4rem;text-align:right;left:-1rem;background:hsla(0,0%,100%,.2)}.valine .vlist .vcard section .vfooter .vat{color:#b3b3b3}.valine .vlist .vcard section .vfooter .vat:hover{color:#6db33f}.vcontent img{margin:0}.valine .info{display:none}</style><script type="text/javascript" src="/js/av.min.js"></script><script type="text/javascript" src="/js/Valine.min.js"></script><script type="text/javascript" src="/js/activate-power-mode.js"></script><script>POWERMODE.colorful=!0,POWERMODE.shake=!1,document.body.addEventListener("input",POWERMODE),new Valine({el:"#comment-div",notify:!1,verify:!0,appId:"SMcDFP1bN1jgb9Lo8JmtICHm-gzGzoHsz",appKey:"dH4nrUrt3V5XiJiI6Qyejnbi",placeholder:"",path:window.location.pathname,avatar:"monsterid",guest_info:["nick","mail","link"]});var chicken='<a href="#"><img src="https://image.uisdc.com/wp-content/uploads/2018/06/uisdc-chat-chicken.gif" class="checken"></a>';$("#comment-div").prepend(chicken)</script></div></div><script>var $bqinline=$("img[alt='bq-inline']");$bqinline.css({width:"2.3rem",height:"2.3rem",display:"inline","vertical-align":"text-bottom"})</script></div><div class="comments" id="comments"></div></div><aside id="sidebar" class="sidebar" onselectstart="return!1"><div class="sidebar-inner"><ul class="sidebar-nav motion-element"><li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">Contents</li><li class="sidebar-nav-overview" data-target="site-overview">Site Preview</li></ul><section class="site-overview sidebar-panel"><div class="sidebar-sticky sticky"><div itemscope itemtype="https://mrbird.cc"><div class="author__header"><div class="author__avatar"><img src="/images/blogImage.jpg" class="author__avatar" alt="MrBird" itemprop="image"></div><div class="author__content"><div class="author__name" itemprop="name">MrBird</div><p class="author__bio" itemprop="description">A simple blog, code repository, just keep blogging</p></div><div class="author__count"><a href="/archives" class="ignore-href"><span class="count">14</span> <span>Archives</span> </a><a href="/tags" class="ignore-href"><span class="count">2</span> <span>Labels</span></a></div></div><div class="author__urls-wrapper"><ul class="author__urls social-icons"><li><a href="/" itemprop="url" class="ignore-href">🏠 Home</a></li><li><a href="/archives" itemprop="url" class="ignore-href">📦 Archives</a></li><li><a href="/tags" itemprop="url" class="ignore-href">🔖 Labels</a></li><li><a href="/friends" itemprop="url" class="ignore-href">👬 Friends</a></li><li><a href="javascript:;" class="popup-trigger animsition-link">🔍 Search</a></li></ul></div></div></div></section><section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active"><div class="post-toc"><div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#类结构"><span class="nav-number">1.</span> <span class="nav-text">类结构</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#方法解析"><span class="nav-number">2.</span> <span class="nav-text">方法解析</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#构造函数"><span class="nav-number">2.1.</span> <span class="nav-text">构造函数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#put-K-key-V-value"><span class="nav-number">2.2.</span> <span class="nav-text">put(K key, V value)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#rehash"><span class="nav-number">2.3.</span> <span class="nav-text">rehash()</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#get-Object-key"><span class="nav-number">2.4.</span> <span class="nav-text">get(Object key)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#remove-Object-key"><span class="nav-number">2.5.</span> <span class="nav-text">remove(Object key)</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#和HashMap对比"><span class="nav-number">3.</span> <span class="nav-text">和HashMap对比</span></a></li></ol></div></div></section></div><div id="asider-footer"><div id="links"><li><a href="https://love.mrbird.cc" target="_blank" itemprop="url" class="ignore-href"><i class="fa fa-fw fa-diamond" aria-hidden="true"></i></a></li><li><a href="https://cloud.mrbird.cn" target="_blank" itemprop="url" class="ignore-href"><i class="fa fa-fw fa-skyatlas" aria-hidden="true"></i></a></li><li><a href="https://gitee.com/mrbirdd" target="_blank" itemprop="sameAs" class="ignore-href"><i class="fa fa-fw fa-codepen" aria-hidden="true"></i></a></li><li><a href="https://github.com/wuyouzhuguli" target="_blank" itemprop="sameAs" class="ignore-href"><i class="fa fa-fw fa-github-alt" aria-hidden="true"></i></a></li></div><div id="author"></div><script type="text/javascript">var $smsheoschzd100dn="@ 2016 - "+(new Date).getFullYear()+" MrBird";document.getElementById("author").innerHTML=$smsheoschzd100dn</script><div><script type="text/javascript" src="/js/busuanzi.js"></script> UV <span class="busuanzi-value" id="busuanzi_value_site_uv" style="cursor:pointer" title="统计开始时间：2019年7月5日"></span> PV <span class="busuanzi-value" id="busuanzi_value_site_pv" style="cursor:pointer" title="统计开始时间：2019年7月5日"></span></div></div><script>function c__(){var o=sidebar_nav_toc.attr("class");o.indexOf("active")!=-1?footer.hide(300):footer.show(300)}var sidebar_nav_toc=$(".sidebar-nav-toc"),footer=$("#asider-footer");c__(),$(".sidebar-nav").on("click",function(){c__()})</script></aside></div></main><div class="back-to-top"><span id="scrollpercent"><span>0</span></span></div></div><script type="text/javascript">"[object Function]"!==Object.prototype.toString.call(window.Promise)&&(window.Promise=null)</script><script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script><script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script><script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script><script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script><script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script><script type="text/javascript" src="/js/src/utils.js?v=5.1.1"></script><script type="text/javascript" src="/js/src/motion.js?v=5.1.1"></script><script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.1"></script><script type="text/javascript" src="/js/src/post-details.js?v=5.1.1"></script><script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.1"></script><script type="text/javascript">function proceedsearch(){$("body").append('<div class="search-popup-overlay local-search-pop-overlay"></div>').css("overflow","hidden"),$(".search-popup-overlay").click(onPopupClose),$(".popup").toggle();var t=$("#local-search-input");t.attr("autocapitalize","none"),t.attr("autocorrect","off"),t.focus()}var isfetched=!1,isXml=!0,search_path="search.xml";0===search_path.length?search_path="search.xml":search_path.endsWith("json")&&(isXml=!1);var path="/"+search_path,onPopupClose=function(t){$(".popup").hide(),$("#local-search-input").val(""),$(".search-result-list").remove(),$("#no-result").remove(),$(".local-search-pop-overlay").remove(),$("body").css("overflow","")},searchFunc=function(t,e,o){"use strict";$("body").append('<div class="search-popup-overlay local-search-pop-overlay"><div id="search-loading-icon"><i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i></div></div>').css("overflow","hidden"),$("#search-loading-icon").css("margin","20% auto 0 auto").css("text-align","center"),$.ajax({url:t,dataType:isXml?"xml":"json",async:!0,success:function(t){isfetched=!0,$(".popup").detach().appendTo(".header-inner");var n=isXml?$("entry",t).map(function(){return{title:$("title",this).text(),content:$("content",this).text(),url:$("url",this).text()}}).get():t,r=document.getElementById(e),s=document.getElementById(o),a=function(){var t=r.value.trim().toLowerCase(),e=t.split(/[\s\-]+/);e.length>1&&e.push(t);var o=[];if(t.length>0&&n.forEach(function(n){function r(e,o,n,r){for(var s=r[r.length-1],a=s.position,i=s.word,l=[],h=0;a+i.length<=n&&0!=r.length;){i===t&&h++,l.push({position:a,length:i.length});var p=a+i.length;for(r.pop();0!=r.length&&(s=r[r.length-1],a=s.position,i=s.word,p>a);)r.pop()}return c+=h,{hits:l,start:o,end:n,searchTextCount:h}}function s(t,e){var o="",n=e.start;return e.hits.forEach(function(e){o+=t.substring(n,e.position);var r=e.position+e.length;o+='<b class="search-keyword">'+t.substring(e.position,r)+"</b>",n=r}),o+=t.substring(n,e.end)}var a=!1,i=0,c=0,l=n.title.trim(),h=l.toLowerCase(),p=n.content.trim().replace(/<[^>]+>/g,""),u=p.toLowerCase(),f=decodeURIComponent(n.url),d=[],g=[];if(""!=l&&(e.forEach(function(t){function e(t,e,o){var n=t.length;if(0===n)return[];var r=0,s=[],a=[];for(o||(e=e.toLowerCase(),t=t.toLowerCase());(s=e.indexOf(t,r))>-1;)a.push({position:s,word:t}),r=s+n;return a}d=d.concat(e(t,h,!1)),g=g.concat(e(t,u,!1))}),(d.length>0||g.length>0)&&(a=!0,i=d.length+g.length)),a){[d,g].forEach(function(t){t.sort(function(t,e){return e.position!==t.position?e.position-t.position:t.word.length-e.word.length})});var v=[];0!=d.length&&v.push(r(l,0,l.length,d));for(var C=[];0!=g.length;){var $=g[g.length-1],m=$.position,x=$.word,w=m-20,y=m+80;w<0&&(w=0),y<m+x.length&&(y=m+x.length),y>p.length&&(y=p.length),C.push(r(p,w,y,g))}C.sort(function(t,e){return t.searchTextCount!==e.searchTextCount?e.searchTextCount-t.searchTextCount:t.hits.length!==e.hits.length?e.hits.length-t.hits.length:t.start-e.start});var T=parseInt("1");T>=0&&(C=C.slice(0,T));var b="";b+=0!=v.length?"<li><a href='"+f+"' class='search-result-title'>"+s(l,v[0])+"</a>":"<li><a href='"+f+"' class='search-result-title'>"+l+"</a>",C.forEach(function(t){b+="<a href='"+f+'\'><p class="search-result">'+s(p,t)+"...</p></a>"}),b+="</li>",o.push({item:b,searchTextCount:c,hitCount:i,id:o.length})}}),1===e.length&&""===e[0])s.innerHTML='<div id="no-result"><i class="fa fa-search fa-5x" /></div>';else if(0===o.length)s.innerHTML='<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>';else{o.sort(function(t,e){return t.searchTextCount!==e.searchTextCount?e.searchTextCount-t.searchTextCount:t.hitCount!==e.hitCount?e.hitCount-t.hitCount:e.id-t.id});var a='<ul class="search-result-list">';o.forEach(function(t){a+=t.item}),a+="</ul>",s.innerHTML=a}};r.addEventListener("input",a),$(".local-search-pop-overlay").remove(),$("body").css("overflow",""),proceedsearch()}})};$(".popup-trigger").click(function(t){t.stopPropagation(),isfetched===!1?searchFunc(path,"local-search-input","local-search-result"):proceedsearch()}),$(".popup-btn-close").click(onPopupClose),$(".popup").click(function(t){t.stopPropagation()}),$(document).on("keyup",function(t){var e=27===t.which&&$(".search-popup").is(":visible");e&&onPopupClose()})</script></body><script>$(function(){$("a").not(".nav-link,.cloud-tie-join-count,.ignore-href,.jstree-anchor").addClass("animsition-link")});var burst1=new mojs.Burst({left:0,top:0,radius:{5:40},children:{shape:"circle",fill:["red","cyan","orange"],fillOpacity:.8,radiusX:3.5,radiusY:3.5}});document.addEventListener("click",function(a){null==a.target.href&&"footer"!=a.target.className&&"copyright"!=a.target.className&&"author__urls social-icons"!=a.target.className&&"author__avatar"!=a.target.className&&"sidebar sidebar-active"!=a.target.className&&burst1.tune({x:a.pageX,y:a.pageY}).generate().replay()})</script><script type="text/javascript" src="/js/message.js"></script></html><!-- rebuild by neat -->