一文帶你玩轉offer-01

文章目錄

• 1.RabbitMq是如何實作消息路由的
• • 1.1 工作流程
  • 1.2 路由政策
  • • Direct Exchange
    • Topic Exchange
    • Fanout Exchange
• 2.談談你對時間輪的了解
• • 2.1 什麼是時間輪
  • 2.2 時間輪的工作原理
  • 2.3 時間輪優缺點分析
• 3.什麼是幂等？如何解決幂等性問題
• • 3.1 什麼是幂等
  • 3.2 如何解決幂等性問題
• 4.在秒殺場景中，常見的限流算法有哪些
• • 4.1 計數器限流算法
  • 4.2 滑動視窗限流算法
  • 4.3 漏桶限流算法
  • 4.4 令牌桶限流算法
• 5.Spring中的Bean是線程安全的嗎？
• 6.談談你對Spring Bean的了解
• 6.1 什麼是Spring Bean
• • 6.2 定義Spring Bean有哪些方式
  • 6.3 Spring容器是如何加載Bean的
• 7.Spring為何需要三級緩存解決循環依賴而不是二級緩存
• • 7.1什麼是循環依賴
  • 7.2 哪些情況會出現循環依賴
  • 7.3 Spring如何解決循環依賴
  • 7.4 Spring中哪些情況下不能 解決循環依賴問題
• 8.簡述Spring MVC的執行流程
• • 8.1 配置階段
  • 8.2 初始化階段
  • 8.3 運作階段
• 9.簡述Spring Aop原理
• • 9.1 建立代理對象階段
  • 9.2 攔截目标對象階段
  • 9.3 調用代理對象階段
  • 9.4 調用目标對象階段
• 10.單線程下HashMap的工作原理
• • 10.1 HashMap中的關鍵屬性
  • 10.2 HashMap的工作原理

本節已全部更新完成

1.RabbitMq是如何實作消息路由的

1.1 工作流程

RabbitMq:一個基于

AMQP協定實作的分布式消息中間件

AMQP的工作機制如下圖所示 ：

首先生産者把消息發送到RabbitMQ Broker上的Exchange交換機上，Exchange交換機會把收到的消息根據

路由規則分發給綁定的隊列

，最後再把消息投遞給訂閱了這個隊列的消費者進而去完成消息的異步通信。

其中Exchange交換機就可以去定義這個消息的路由規則，将消息去路由到指定的隊列，然後隊列就是

消息的載體

，每個消息就可以根據路由規則路由到一個或者多個隊列中。

1.2 路由政策

完成RabbitMq路由的核心元件是

Exchange交換機

，而消息的路由又是由Exchange類型（交換機類型）和Binding決定的。

Binding是表示在

隊列和交換機

之間的一個綁定關系，那麼每個綁定關系會存在一個BindingKey，通過這種方式相當于是在Exchange交換機中建立了一個路由關系表，在每個生産者發送消息的時候，

需要聲明一個RoutingKey（路由鍵）

，Exchange拿到RoutingKey之後，根絕RoutingKey和路由表裡面的BindingKey進行比對，而比對的規則是通過Exchange類型來決定的

在 RabbitMq中預設有四種類型，常用的有三種：

• Direct
• Fanout
• Topic

Direct Exchange

其中Direct叫做直連，也就是完整的比對方式，他需要Routing Key和Binding Key

完全一緻

，相當于是

點對點的發送

，原理如下圖所示：

如果發生了Routing Key為spring的消息，隻有一個隊列能接受到消息

Topic Exchange

Topic叫做主題，那麼這種方式是通過

設定通配符來動态比對

，類似于正則，就是用Routing Key去比對Binding Key,Binding Key支援兩個通配符：

• #号代表0個或多個單詞
• *号代表比對不多不少一個單詞

另外Binding Key是用 點隔開兩個單詞，是以*和#就相當于是正規表達式的一個作用

我們有4個隊列綁定到 Topic類型的交換機中，而且使用的是不同的綁定鍵，如上圖所示，那麼如果我們發送routing key為“junior.abc.jvm”的消息，那麼隻有第一個隊列可以收到。

如果我們發送routing key為“senior.netty”的消息，那麼第二個隊列第三個隊列都可以收到。

Fanout Exchange

Fanout叫做廣播，這種方式是不需要設定Routing key的，而且他會把消息廣播給綁定到目前Exchange上的所有隊列上，如下圖所示：

我們隻需要發送消息到Fanout的Exchange上，那麼3個隊列都會收到消息。

目前主流的分布式中間件有：

• Rabbit Mq
• Kafka
• Rocket Mq

2.談談你對時間輪的了解

2.1 什麼是時間輪

時間輪：一種用來

存儲定時任務的環狀數組

。

他的工作原理和鐘表的表盤類似，他有兩個部分組成：

• 環形數組
• 周遊環形數組的指針

首先要定義一個固定長度的環形數組，然後數組的每一個元素代表一個時間刻度，假設每個刻度之間的間隔是1s，那麼長度為8s的數組就代表8秒鐘。

然後就是需要有一個指針，那麼這個指針是按照順時針的方向，無限的循環這個數組，每隔一個

最小的時間機關

就前進一個數組的索引，那麼這個指針完整的轉一圈的話就代表8秒鐘，轉一圈的話就代表16秒鐘，假設從0點0分0秒開始，轉一圈之後就到了0點0分9秒

2.2 時間輪的工作原理

環形數組裡面的每一個元素，都是用來

存儲定時任務的容器

，當我們向時間輪裡

添加一個定時任務

的時候，我們會根據

定時任務的執行時間計算他所存儲的數組下标

,當然會在某個時間刻度上會存在多個定時任務，那麼這個時候就會采用

雙向連結清單

的方式進行存儲。

當我們的指針指向某個數組的時候，就會把這個數組中存儲的任務取出來，然後就周遊這個連結清單，逐個去運作這個連結清單中的任務

那麼如果某個定時任務的執行時間，大于環狀數組的長度，一般就可以

使用一個圈數

來表示該任務的延時執行時間，比如一個第16秒執行的任務，那就意味着這個任務應該在第2圈的數組下标為0的時候去執行。

2.3 時間輪優缺點分析

使用時間輪的方式來管理多個定時任務的好處有很多，我認為有兩個比較重要的優點：

• 1.可以減少定時任務添加和删除的時間複雜度，提升性能
• 2.可以保證每次執行定時任務都是o(1)的複雜度，在定時任務執行密集的情況下，性能優勢十分明顯

當然時間輪也有缺點：對于執行時間非常嚴格的任務，時間輪不是很合适，因為時間輪算法的精度取決于最小時間單元的粒度，假設以1秒為時間刻度的話，那麼小于1s的任務就無法被時間輪排程

同時時間輪算法在很多架構中都有用到，比如說:Dubbo，Netty，Kafka等。

3.什麼是幂等？如何解決幂等性問題

3.1 什麼是幂等

幂等是一個數學上的概念，而在計算機程式設計領域中幂等是指

一個方法任意多次執行所産生的影響均與一次執行的影響相同

。

簡單來說：一個邏輯即使被重複執行多次，也不影響最終結果的一緻性。

之是以要考慮幂等性問題，主要是因為在網絡通訊中有兩種行為都有可能導緻我們的接口被重複執行：

• 1.使用者重複送出或者使用者的惡意攻擊會導緻重複執行
• 2.在分布式系統中，為了去避免資料的丢失，采用的 逾時重試機制

是以在我的程式設計中對于資料變更操作的接口都要去保證接口的幂等性，而幂等性的核心思想，其實就是

保證這個接口的執行結果隻影響一次，後續再次調用，也不能對資料産生影響

。

是以基于這個需求呢，如何去解決幂等性呢？

3.2 如何解決幂等性問題

解決幂等性問題的方法有很多，下面我分享一下一些常用的解決方案：

• 1.使用資料庫的唯一限制來實作幂等。

比如說對于資料插入的場景而言，假設我們要建立一個訂單，因為訂單号肯定是唯一的，是以如果我們多次去調用資料庫的唯一限制，他就會産生異常，進而去避免一個請求建立多個訂單的問題。

• 2.使用redis提供的setNX

比如說我們對于MQ的消息的場景，我們要去避免MQ重複消費，進而導緻資料多次被修改的問題，可以在接受MQ消息的時候把這個消息通過setNX寫入到redis中，一旦這個消息被消費之後，我們就就不會被再次消費

• 3.使用狀态機來實作幂等，所謂狀态機是指一條資料的完整的運作狀态的轉化流程

比如說訂單的狀态，因為他的狀态隻會向前變更，是以多次修改同一條資料的時候一旦狀态發生改變，那麼這條資料修改造成的影響也隻會發生一次。

除了以上三種方法之外，我們還可以通過token機制或者去增加重表的方法來實作幂等。

但是無論使用何種方法，無非也就是兩種思路，要麼就是接口隻允許調用一次，比如說唯一限制、基于Redis的鎖機制，要麼就是對資料的影響隻會發生一次，比如說悲觀鎖、樂觀鎖等等。

4.在秒殺場景中，常見的限流算法有哪些

所謂限流就是指限制流量請求的頻次，它主要是在我們的高并發的情況下，用于去保護系統的一種政策，主要是

避免在流量高峰的時候導緻系統崩潰，進而造成系統不可用的問題

。

實作限流的常見算法有4種：

• 計數器限流算法
• 滑動視窗限流算法
• 漏桶限流算法
• 令牌桶限流算法

下面我給大家詳細介紹一下每種算法的基本原理

4.1 計數器限流算法

這種算法一般用在

單一次元的通路頻率限制上

比如說短信驗證碼每隔60s發送一次，或者說接口的調用次數等等。

他的實作方法十分簡單：每調用1次就會加1，處理結束以後就會減1

4.2 滑動視窗限流算法

其本質上也是一種

計數器

，隻不過是通過以

時間為次元的可滑動的視窗設計來減少臨界值帶來的并發超過門檻值的問題

，那麼進行資料統計的時候，我們隻需要統計這個視窗内每個時刻的通路量就可以了，比如說Spring Cloud中的

Hystrix

以及Spring Cloud Alibaba中的

Sentinel

都是采用滑動視窗來實作的。

4.3 漏桶限流算法

他是一種

恒定速率

的限流算法，不管他的請求量是多少，服務端的處理效率都是恒定的，比如說

基于MQ來實作的生産者和消費者模型

其實就是一種漏桶限流算法

4.4 令牌桶限流算法

相對于漏桶限流算法來說，他的核心思想是

令牌桶以恒定速率去生成令牌

，儲存到令牌桶裡，桶的大小是

固定的

，當我們的令牌桶滿了以後就不會在生成令牌，是以每個客戶請求進來以後就

必須要到令牌桶中去擷取一個令牌

才可以通路，否則就會排隊等待。

在流量低峰的時候，令牌桶就會出現堆積，是以當出現限流高峰的時候，我們需要有足夠多的令牌可以擷取，是以令牌桶他能夠

允許瞬時流量的處理

，比如說我們

網關層面的限流或者是接口層面的限流

都可以使用令牌桶的算法。像Google的Guava和Redssion的限流都是使用了令牌桶的算法。

限流的本質是

實作系統的保護

，最終選擇什麼樣的算法，一方面取決于

統計的精準度

，另一方面考慮

限流次元和場景的需求

。

5.Spring中的Bean是線程安全的嗎？

先說一下答案：

其實Spring中的Bean是否線程安全跟 Spring本身無關 ，Spring架構中會提供很多線程安全的的政策，是以Spring容器中的Bean本身也不具備線程安全的特性。

要徹底了解上面這個結論，我們首先要知道Spring中的Bean是從哪裡來的，在Spring容器中，除了很多Spring内置的Bean以外，其實其它Bean都是我們自己通過

Spring配置來聲明的

，然後由Spring容器來

進行統一的管理和加載

。

我們在Spring聲明配置中通常會配置以下内容：

• class（全類名）
• id (Bean的唯一辨別)
• scope（作用域）
• lazy-init (是否延時加載)

之後呢，Spring容器會根據這些配置的内容，使用對應的政策來進行建立執行個體，是以Spring容器中的Bean，其實都是根據我們自己寫的類來建立的執行個體。

Spring中的Bean是否線程安全，跟Spring容器無關，隻是交給Spring容器托管而已，那麼在Spring容器中什麼樣的Bean會存線上程安全問題呢？

在解答這個問題之前，我們得先回顧一下Spring Bean的作用域。

• prototype（多例Bean） 每次getBean的時候都會建立一個新的對象
• singleton（單例Bean） 在Spring容器中隻會存在一個全局共享的執行個體

根據作用域的定義，

多例Bean

每次都會建立新的執行個體，也就是說線程之間

不存在

Bean共享的問題，是以多例Bean是不存線上程安全問題的。

而單例Bean是所有線程

共享一個執行個體

，是以可能會存線上程安全問題。但是呢，單例Bean又分為：

• 無狀态Bean 在多線程操作中 隻會對Bean的成員變量進行查詢操作 ，不會修改成員變量的值，這樣的Bean成為無狀态Bean，是以無狀态的單例Bean 不存線上程安全問題 。
• 有狀态Bean 多線程操作中，如果需要對Bean中的成員變量進行 資料更新操作 ，這種Bean成為有狀态Bean，而有狀态Bean 可能存線上程安全問題 。

在Spring中，隻有有狀态的單例Bean才會存線上程安全問題，我們在使用Spring的過程中經常會使用到有狀态的單例Bean，如果我們經常遇到線程安全問題，我們又該如何處理呢？

• 1.修改Bean的作用域，将"singleton"改為"prototype"
• 2.避免定義可變的成員變量
• 3.在類中定義 ThreadLocal的成員變量 ，并将需要的可變成員變量儲存在ThreadLocal中，因為ThreadLocal本身就具備 線程隔離的特點 ，這就相當于為每個線程提供了一個 獨立的變量副本 ，每個線程呢隻需要操作自己的線程變量副本，進而解決線程安全的問題。

6.談談你對Spring Bean的了解

回答這個問題，我們可以從三個方面來回答：

• 1.什麼是Spring
• 2.定義Spring Bean有哪些方式
• 3.Spring容器是如何加載Bean的

6.1 什麼是Spring Bean

Spring Bean是Spring中最基本的組成單元，Spring官方文檔對Bean的解釋是：

In Spring, the objects that form the backbone of your application and that are managed by the Spring IoC container are called beans. A bean is an object that is instantiated, assembled, and otherwise managed by a Spring IoC container.

翻譯過來就是：

在 Spring 中，構成應用程式主幹并由 Spring IoC 容器管理的對象稱為 bean。bean 是由Spring IoC 容器執行個體化、組裝和管理的對象。

根據官方的定義呢，我們可以提取出來以下資訊：

• 1.Bean是對象，一個或多個不限定；
• 2.Bean是托管在Spring中的一個IOC容器中；
• 3.我們的程式是由一個一個的Bean組成的

Spring Bean是通過聲明式配置的方式來定義Bean的，所有的Bean是需要前置的依賴或者參數。

Spring啟動以後，會解析這些聲明好的配置内容，那麼我又該如何去定義呢？

6.2 定義Spring Bean有哪些方式

Spring Bean定義它的配置有三種方式：

1.基于XML的方式來配置

這種配置方式主要适用于以下兩場景：

• 1.Bean實作類來自第三方的類庫，比如DataSource等；
• 2.需要定義命名空間的配置，如：Context，aop，mvc等；

2.基于注解掃描的方式來配置

這種配置方式主要适用于在開發中需要引用類，如Controller、Service、Dao等。

Spring提供了四個注解：

• [email protected]，聲明為控制層元件的Bean
• [email protected]，聲明為業務邏輯層元件的Bean
• [email protected]，聲明為資料通路層元件的Bean
• [email protected]，對元件的層次難以定位的時候使用

3.基于Java類的配置

該方式主要适用于以下兩類場景：

• 1.需要通過代碼控制對象建立邏輯的場景
• 2.實作零配置，消除XML配置檔案的場景

使用基于類的配置需要以下步驟：

• 1.首先在BeanConfiguration類上配置@Configuration注解，表示将BeanConfiguration這樣的一個類定義為Bean的中繼資料
• 2.在方法上使用@Bean注解，這個方法預設就是Bean的名稱，那麼方法的傳回值就是Bean的執行個體
• 3.通過AnnotationConfigApplicationContext或子類來啟動Spring容器，進而加載這些聲明好的注解的配置。

6.3 Spring容器是如何加載Bean的

上面我們提到了，無論是基于注解，還是基于xml，或者是基于properties配置檔案的方式來來存儲對象所需要的一些必要的資訊（如對象的屬性，方法等），我們将這些建立對象所需要的必要資訊稱為配置元資訊。

Spring會将這些資訊都轉化為一個叫做

BeanDefination的對象

。那麼BeanDefination中幾乎儲存了所有的配置檔案中聲明的内容。而BeanDefination放入一個

Map結構中

，

以beanName作為Key

，

以BeanDefination對象作為value

，之後Spring容器會根據beanName找到對應的BeanDefination，然後再去選擇具體的建立政策。

7.Spring為何需要三級緩存解決循環依賴而不是二級緩存

7.1什麼是循環依賴

指循環引用，是兩個或多個Bean互相之間的持有對方的引用

在代碼中，如果有兩個或多個Bean之間持有對方的引用的話，Spring就會對它進行一個注入指派，也就是自動給屬性指派，那麼Spring給屬性指派的時候，将會導緻死循環。

7.2 哪些情況會出現循環依賴

循環依賴有三種形态：

1.互相依賴

2.三者之間的依賴

3.自我依賴

7.3 Spring如何解決循環依賴

Spring解決循環依賴的方法就是通過三級緩存來實作

• 三級緩存：存放的是一個對象的半成品
• 二級緩存：存放的是一個提前暴露出來的對象
• 一級緩存：存放的是一個完全初始化的對象

當我們建構a的時候，a會作為一個

半成品放到三級緩存中

，此時發現a中有一個b屬性需要注入，這個時候就會去Spring容器中找有沒有b屬性，如果有b屬性就直接拿出來；如果沒有，這個時候就會再去初始化b類。

在初始化b時，它和a一樣，

也要放到三級緩存中

，但是呢發現初始化b時需要a屬性，此時還是一樣會去Spring容器中去找，會發現在三級緩存中有a，于是就把a從三級緩存

提前暴露到

二級緩存，交給b去做一個注入，這時a注入好了之後，b就可以從三級緩存放到一級緩存了。

同時我們最開始建立b的原因就是a需要這個b，是以說，二級緩存中的a，就拿到了放在一級緩存裡的b，這樣，Spring就很完美的解決了循環依賴問題。

7.4 Spring中哪些情況下不能 解決循環依賴問題

第一種情況就是多例Bean通過setter方式注入

第二種 情況是構造器注入的Bean

第三種情況是單例的代理Bean通過setter注入

第四種情況是設定了@DependsOn的Bean

8.簡述Spring MVC的執行流程

SpringMVC的詳細執行流程分為三個階段：

• 1.配置階段
• 2.初始化階段
• 3.運作階段

8.1 配置階段

配置階段主要是完成對

xml的配置和注解的配置

。

具體步驟如下：

從

web.xml

開始，配置

DispatchServlet的url比對規則

，和Spring主配置檔案中的一個加載路徑（contextConfigLocation=‘classpath:applicationContext’）。

然後呢，配置注解，比如說@Controller，@Service，@Autowired以及RequestMapping。

8.2 初始化階段

主要是去

加載并解析配置資訊以及IOC容器

，還有

DI操作和HandlerMapping的一個初始化

，具體步驟如下：

web容器啟動以後會由web容器自動調用DispatchServlet的

init()

方法，在init()方法中，會初始化IOC容器，

IOC容器其實就是一個Map

，緊接着根據配置好的

掃描包的路徑

然後掃描出相關的類，并且使用

反射

對它進行執行個體化，然後

緩存到IOC容器中

，緩存之後，Spring容器再次疊代，掃描IOC容器的執行個體，給需要自動指派的屬性自動指派。

哪些屬性需要自動指派呢？

比如加了@Autowired的屬性

最後在去讀取@RequestMapping的注解，擷取它

請求的URL

，然後将URL和Method建立一個一對一的映射關系，并且緩存起來，簡單概括下來就是：

緩存在一個Map中，他的key就是url，它的value是Method。

8.3 運作階段

運作階段在Spring啟動以後，等待使用者請求，然後完成内部的排程，并且響應結果。具體步驟如下：

使用者在浏覽器中輸入url之後，web容器會接受到使用者的請求，web容器會自動調用

doGet()或者doPost()

方法，然後從doGet()或者doPost()方法中，可以獲得兩個對象，分别是

request對象和response對象

，通過request對象，可以獲得使用者

請求過來的資訊

，通過response對象，可以往

浏覽器輸出背景響應的結果

根據request中獲得的請求url，從

HandlerMapping

中找到url對應的Method，然後接着利用

反射去調用方法

，然後将

方法的傳回結果作為響應結果傳回給浏覽器

。

最後使用者就可以看到我們最終的響應結果

9.簡述Spring Aop原理

Spring AOP大緻分為四個階段：

• 建立代理對象
• 攔截目标對象
• 調用代理對象階段
• 調用目标對象階段

9.1 建立代理對象階段

在Spring中建立Bean的執行個體都是從

getBean

方法開始，在執行個體建立之後Spring容器會根據AOP的配置去

比對目标類的類名

，看目标類是否滿足切面規則，如果滿足切面規則，就會調用

ProxyFactory

建立Bean，并且

緩存到IOC容器中

，然後根據目标對象自動選擇不同的代理政策：

• 如果目标類 實作了接口 ，Spring會預設使用JDK Proxy
• 如果目标類 沒有 實作接口，Spring會預設選擇Cglib Proxy

當然我們也可以通過配置去強制Spring使用Cglib Proxy

9.2 攔截目标對象階段

當使用者調用目标對象的某個方法的時候，就會被一個叫做

AopProxy

的對象攔截，那麼Spring将所有的調用政策

封裝

到了這個對象中，它

預設實作

了一個叫做

InvocationHandler

的接口，也就是調用代理對象的

外層攔截器

，在這個接口的invoke()方法中，會觸發MethodInvaocation的proceed()方法，在proceed()方法中，會按照

順序執行

符合AOP規則的攔截器鍊。

9.3 調用代理對象階段

Spring Aop攔截鍊中

每個元素都會被命名為MethodInterceptor

，也就是

切面中的Advice通知

，這個通知是可以用來

回調

的，簡單的了解就是生成的代理Bean方法，也就是我們常說的被織入的代碼片段，這些被織入的代碼片段會在該階段被執行。

9.4 調用目标對象階段

MethodInterceptor接口也有一個invoke()方法，那麼在MethodInterceptor的invoke()方法中，會觸發對

目标對象的調用

，也就是去

反射調用

目标對象的方法。

下面說幾個重要的名詞：

• 代理對象：就是由Spring代理政策生成 的對象
• 目标對象：就是我們自己寫的業務代碼
• 織入代碼：在我們自己寫得業務代碼中增加的代碼片段
• 切面通知：封裝織入代碼片段的回調方法
• MethodInvocation：負責執行攔截器鍊，在proceed()方法中去執行
• MethodInterceptor：負責執行織入片段的代碼，在Invoke()方法中去執行

10.單線程下HashMap的工作原理

HashMap是基于Hash表對Map接口的實作類，它的特點是

通路資料速度快

，并且不是按照順序來周遊。

HashMap提供所有的可選的映射操作，但是

不能保證映射的順序不變

，并且允許插入

空值和空鍵

，HashMap本身并

不是線程安全

的，當存在多線程同時寫入的時候，可能會導緻

資料不一緻

的情況，

10.1 HashMap中的關鍵屬性

要透徹了解HashMap原理，首先我們要對以下幾個關鍵的屬性有一個基本的認識

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    transient int size;
    transient int modCount;
           

上面是HashMap的源碼片段

• LOAD_FACTOR:負載因子，預設值0.75，表示在擴容前，HashMap空間填滿程度的邊界
• THRESHOLD：記錄HashMap所能夠容納的鍵值對邊界，計算規則是：負載因子*數組長度
• size：用來記錄HashMap實際存在的鍵值對的數量
• modCount：用來記錄HashMap記憶體結構發生變化的次數
• DEFAULT_INITIAL_CAPACITY：HashMap的預設容量值，預設是16

HashMap采用的是數組+連結清單+紅黑樹(JDK 1.8)的一個存儲結構

HashMap的數組部分稱為

Hash桶

，數組元素儲存在一個叫做table的屬性中，當連結清單長度

大于8

時，連結清單的資料将會以

紅黑樹的形式進行存儲

，當連結清單的長度

降到6

時，為連結清單形式存儲

每個Node結點儲存了用來定位數組索引位置的hash值和key、value以及連結清單指向的下一個Node結點。

Node類是HashMap的内部類，它實作了Map.Entry接口，他的本質其實可以簡單了解成就是一個鍵值對。

10.2 HashMap的工作原理

當我們向HashMap插入資料時，首先要确定Node在數組中的位置。

如何去确定Node的位置呢？

我們以key為“e”的字元串為例，HashMap首先會調用hasCode()方法，擷取key的hashCode值為h，然後對h進行一個高位運算，将h右移16位，取得h的高16位，與h的低16位進行異或運算，最後得到h的值，然後在于table.length-1進行與運算，得道對象的保留位，最終擷取數組下标。

其實上面的操作就是求模取餘法，但是乘除運算效率比較低，是以才會有上面的位操作運算，最終計算的效果和 h = h a s h C o d e % ( t a b l e . l e n g t h − 1 ) h=hashCode\%(table.length-1) h=hashCode%(table.length−1)這樣可以保證數組下标不越界。