static final float DEFAULT_LOAD_FACTOR = 0.75f;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
/**
- The number of key-value mappings contained in this map.
*/
transient int size;
/**
-
阈值
-
The next size value at which to resize (capacity * load factor).
-
@serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//实际存储方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {}
//扩容方法
final Node<K,V>[] resize() {}
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//实际取值方法
final Node<K,V> getNode(int hash, Object key) {}
* **用法**
1. put(key,value)
调用hashCode(key)，使用node存储hash,key,value，如果hashcode存在则使用链表存储。
2. get(key)
根据key的hashcode找到Entry，然后获取值对象，如果根据hashcode找到的是个链表，再去根据key.equals()判断，链表中正确的节点。
* **关于扩容**
当HashMap的大小超过了阈值(size> threshold)的时候`(默认的装填因子为0.75，也就是说当一个map填满了它定义容量的75%就会去扩容)`,HashMap大小会扩大到原来的2倍。整个过程类似于创建新的数组，将原数组的元素重新hash后放到新数组中(rehashing)。
> HashMap是非同步的，所以在多线程中使用时需要注意扩容等问题
* **相关概念**
* hashing的概念
* HashMap中解决碰撞的方法
* equals()和hashCode()的应用，以及它们在HashMap中的重要性
* 不可变对象的好处
* HashMap多线程的条件竞争
* 重新调整HashMap的大小
参考地址：[http://www.importnew.com/7099.html]( )
**_以上是网上能搜到的解释，下面是个人总结的知识点提要_**
**如面试遇到此问题，第一步，反问面试官，您说的是哪个版本的HashMap**
* hashmap底层使用 数组+链表 的数据结构，实现存储数据，使用拉链法解决碰撞问题。
* map.put(key,value)的时候，内部会对key进行一次hash算法，得到一个hash值，对这个hash值&操作得到元素在数组中的位置。
* 如果该位置没有元素，那么直接加入，如果发生碰撞了，那么用拉链法，需要遍历链表比较key和hash值，如果有就覆盖，没有就到表尾了，所以会插到表尾。
* 初始容量为16，加载因子0.75，当map添加的元素超过12个的时候会触发扩容机制。数组的容量翻倍，已经存入的元素做rehash的操作，重新在数组中找位置存储。
* java8后改为碰撞链表元素超过8个，用红黑树实现
* java8在表尾，java7是在链表头插入
**思考点：**
什么情况下考虑使用SparseArray和ArrayMap替换HashMap的情况
* * *
### 相关面试题
**1\. 为什么HashMap的容量总是2x？**
从源码中可以看到，当**putVal**方法中，是通过`tab[i = (n - 1) & hash]`得到在数组中位置的。
依稀记得当年在学校中，学到hash算法的时候，学的都是`n%size`运算，来确定数值在数组中的位置，而HashMap中为什么要用到&运算呢。
原因如下
1. 大家都知道&运算要比%运算速度快，虽然可能是几毫米的差别。
2. 在n为2x时，`(n-1)&hash == hash%n`
**为什么容量总是2x？**
首先，Hash算法要解决的一个最大的问题，就是hash冲突，既然不能避免hash冲突，那么就要有个好的算法解决。
而在做&运算时，如果选用非2n的数时，n-1转换为二进制，不能保证后几位全为1，这样做在&hash的运算中，不能做到均匀分布。违背了`(n-1)&hash`的初衷。
(16)10?= 24?= (10000)2
(16-1)10?=(1111)2
假设n的值非2x值，10
(10-1)10?=(1001)2
(19-1)10?=(10011)2
10011
&1111
\=(11)2=(3)10
10011
&1001
\=(1)2=(1)10
同样的%运算，19%16 = 3 ，19%10 = 9。
任意一个数与(1111)2做&运算，都不会因为(1111)2的值而影响到运算结果。
**2\. 如果初始化HashMap的时候定义大小为非2x会影响到计算吗？**
答案是，肯定不会，这种情况JAVA的工程师肯定考虑到了。
源码中我们可以看到，传入的capacity只是影响到了threshold的值，而threshold的值还是通过`tableSizeFor()`确定的。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
在tableSizeFor()方法中。
static final int tableSizeFor(int cap) {
// cap=10
int n = cap - 1;
// n =9 1001
n |= n >>> 1;
// (1001)|(0100)=1101
n |= n >>> 2;
//(1101)|(0011)=1111
n |= n >>> 4;
// (1111)|(0000)=1111
n |= n >>> 8;
// (1111)|(0000)=1111
n |= n >>> 16;
// (1111)|(0000)=1111
//return n+1 = (10000)=16
//确保threshold 为16， 2的4次幂
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
在putVal()方法中，如果第一次添加值，那么`table==null`，会进入到`resize()`方法中，这个时候，就会用到threshold创建新的Node数组。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//第一次添加值，table==null; oldCap = 0;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//将threshold的值设置为oldThr，下面创建table的时候用到
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
....
}
else if (oldThr > 0)
//通过threshold设置新数组容量
newCap = oldThr;
else {
....
}
if (newThr == 0) {
....
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//通过threshold设置table的初始容量
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
....
return newTab;
}
通过以上操作，不论初始化HashMap的时候，传入的容量是多少，都能保证HashMap的容量是2x。
Handler源码分析
===========
一直在纠结一个事，因为自己不爱看大段的文字。
自己写总结的时候到底要不要贴上部分源码。
后来硬着头皮加上了，因为源码里很多东西比自己写的清楚。
RTFSC
### 相关概念
> Handler Message MessageQueue Looper ThreadLocal
Handler机制的完整流程
1. Message#obtain()
2. Handler#
3. Handler#send/post
4. MQ#enqueueMessage() \*_消息的排序_
5. Looper#prepareMainLooper()
6. Looper#prepare()
7. ThreadLocal机制
8. Looper#loop()
9. MQ#next() \*_延迟消息的处理_
10. Handler#dispatchMessage()
**Message#obtain()**
> message中的变量自己去看源码，**target,callback,when**
从handler或者是message的源码中都可以看到，生成Message的最终方法都是调用obtain。
ps:如果你非要用Message的构造方法，那么看清楚他的注释，构造方法上面的注释写的也很清楚，
/**
* Constructor (but the preferred way to get a Message is to call {@link #obtain() Message.obtain()}).
*/
public Message() {
}
下面来分析一波obtain()方法：
1. 为什么上来就是一个同步？
任意线程都可以创建message，所以为了维护好内部的messge池，加锁
2. sPool是个什么东西
字面上看是个池子，但是从定义上看，是一个Message。为什么还要说成一个message池呢？因为Message内部有个next变量，Message做成了一个链表的形式。**这个池子怎么存储message呢？稍后分析源码。**
通过读obtain()的源码，结合链表的知识，很容易理解Message中Spool的原理。
public static final Object sPoolSync = new Object();
private static Message sPool;
private static int sPoolSize = 0;
/**
* Return a new Message instance from the global pool. Allows us to
* avoid allocating new objects in many cases.
*/
public static Message obtain() {
synchronized (sPoolSync) {
if (sPool != null) {
Message m = sPool;
sPool = m.next;
m.next = null;
m.flags = 0; // clear in-use flag
sPoolSize--;
return m;
}
}
return new Message();
}
通过查看调用链，我们能够看到在MQ中enqueueMessage调用了recycle()，而recyle中也是通过链表的形式对sPool进行维护。**源码简单易懂**
下面来看下sPool是怎么维护的。
在recycleUnchecked()同样也是加了锁的。然后就是用链表的形式维护这个池子，size++
public void recycle() {
if (isInUse()) {
if (gCheckRecycle) {
...
}
return;
}
recycleUnchecked();
}
/**
* Recycles a Message that may be in-use.
* Used internally by the MessageQueue and Looper when disposing of queued Messages.
*/
void recycleUnchecked() {
...
synchronized (sPoolSync) {
if (sPoolSize < MAX_POOL_SIZE) {
next = sPool;
sPool = this;
sPoolSize++;
}
}
}
**Handler**
> Handler类的源码总共不超过1000行，并且大部分都是注释，所以我们看该类源码的时候，更多的是看他的注释。**静下心来看源码**
-
构造方法
-
callback对象
-
dispatchMessage
**Handler发送消息(send/post)**
> Handler发送消息的方式分为两种：
>
> 1.post
> 2.send
>
> 不论是post还是send(其他方法)方式，最终都会调用到sendMessageAtTime/sendMessageAtFrontOfQueue。执行equeueMessage，最终调用MQ#enqueueMessage()，加入到MQ中。
**1\. post方式**
以post方式发送消息，参数基本上都是Runnable(**Runnable到底是什么，这个要搞懂**)。post方式发送的的消息，都会调用getPostMessage()，将runnable封装到Message的callbak中，调用send的相关方法发送出去。
ps:个人简单、误导性的科普Runnable，就是封装了一段代码，哪个线程执行这个runnable，就是那个线程。
**2\. send方式**
以send方式发送消息，在众多的重载方法中，有一类比较容易引起歧义的方法，sendEmptyMessageXxx()，这类方法并不是说没有用到message，只是在使用的时候不需要传递，方法内部帮我们包装了一个Message。另一个需要关注的点是:?**xxxDelayed() xxxAtTime()**
**1.xxxDelayed()**
借助xx翻译，得知?**delayed：延迟的，定时的，推迟**?的意思，也就是说，借助这个方法我们能做到将消息延迟发送。e.g：延迟三秒让View消失。ps:在我年幼无知的时候，总是搞懵这个方法，不会用。
在这个方法的参数中，我们看到如果传入的是毫秒值，那么会在delayMillis的基础上与`SystemClock.uptimeMillis()`做个加法。然后执行sendMessageAtTime()。
**`SystemClock.uptimeMillis() 与 System.currentTimeMillis()`的区别自己去研究。**
public final boolean sendMessageDelayed(Message msg, long delayMillis)
{
if (delayMillis < 0) {
delayMillis = 0;
}
return sendMessageAtTime(msg, SystemClock.uptimeMillis() + delayMillis);
}
**2.xxxAtTime()**
在这个方法就更简单易懂了，执行的具体时间需要使用者自己去计算。
在Handler内的equeueMessage中，第一行的`msg.target = this;`,将handler自身赋值到msg.target，标记了这个msg从哪来，**这个要注意后面会用到**。
**MQ#enqueueMessage()**
> 这个方法那是相当的关键
在此之前，我们一直鼓捣一个参数delayMillis/uptimeMillis，在这个方法里参数名变为了**when**，标明这个message何时执行，也是MQ对Message排序存储的依据。MQ是按照when的时间排序的，并且第一个Message最先执行。
在省去了众多目前不关心的代码后，加上仅存的一点数据结构的知识，得到msg在MQ中的存储形式。
`mMessages`位于队列第一位置的msg，新加入到msg会跟他比较，然后找到合适的位置加入到队列中。
ps:记得在一次面试中，面试官问到延迟消息的实现思路，我照着源码说了一下。但是被问到：**每次新加入消息，都要循环队列，找到合适的位置插入消息，那么怎么保证执行效率。**我不知道他这么问是想考我优化这个东西的思路，还是他觉得我说错了。就犹豫了一下，没有怼回去。
boolean enqueueMessage(Message msg, long when) {
...
...
synchronized (this) {
...
...
msg.markInUse();
msg.when = when;
Message p = mMessages;
boolean needWake;
if (p == null || when == 0 || when < p.when) {
msg.next = p;
mMessages = msg;
needWake = mBlocked;
} else {
needWake = mBlocked && p.target == null && msg.isAsynchronous();
Message prev;
for (;;) {
prev = p;
p = p.next;
if (p == null || when < p.when) {
break;
}
if (needWake && p.isAsynchronous()) {
needWake = false;
}
}
msg.next = p; // invariant: p == prev.next
prev.next = msg;
}
...
...
}
return true;
}
以上几步，我们只是将要执行的msg加入到了队列中。接下来分析下什么时候执行msg。
再接再厉，马上就看到暑光了。
**Looper#prepareMainLooper()**
> 借助十几年英语学习积累下来的词汇量，加上我出色的看源码能力。看懂了这个方法的注释及Android系统在哪里执行了此方法。
>
> 面试被问到怎么在子线程创建Looper?
>
> 仔细看注释。Initialize the current thread as a looper....See also: {@link #prepare()}
这个方法，作为开发人员不需要调用它，但是作为一个高级技工还是要多少了解一点的，系统在三个位置调用了此方法，但是我只关心了AndroidThread这个类，AndroidThread是个啥，自己去看吧。
/**
* Initialize the current thread as a looper, marking it as an
* application's main looper. The main looper for your application
* is created by the Android environment, so you should never need
* to call this function yourself. See also: {@link #prepare()}
*/
public static void prepareMainLooper() {
prepare(false);
synchronized (Looper.class) {
if (sMainLooper != null) {
throw new IllegalStateException("The main Looper has already been prepared.");
}
sMainLooper = myLooper();
}
}
**Looper#prepare()**
> 面试的时候经常被问到一个线程可以有多个looper吗？
>
> 看源码注释就得到了答案。
> `throw new RuntimeException("Only one Looper may be created per thread");`
> 怎么保证每个线程只有一个looper呢？这里用到了ThreadLocal。
在自己创建的子线程中，如果想创建Looper，那么只需要调用Looper.prepare()，就会为当前线程创建一个looper了。
private static void prepare(boolean quitAllowed) {
if (sThreadLocal.get() != null) {
throw new RuntimeException("Only one Looper may be created per thread");
}
sThreadLocal.set(new Looper(quitAllowed));
}
**ThreadLocal机制**
> ThreadLocal是个什么东西呢，他是个复杂的机制，毕竟从JAVA1.2就加入了机制，保证了每个线程自己的变量....
>
> 本人简单的、带有误导性的科普是：
>
> 类似一个Map，key是当前线程id，value就是你要保存的值
>
> **一定要自己深入了解该机制**
**Looper#loop()**
> 这个方法也很关键，消息能够执行，起了很大作用。虽然个人感觉能看的代码很少，但是都很精炼啊。
1. 获取looper，得到MQ
2. 循环MQ得到可执行的msg
3. 通过msg自身，去到他该去的地方`msg.target.dispatchMessage(msg);`
# 结语
* 现在随着短视频，抖音，快手的流行NDK模块开发也显得越发重要，需要这块人才的企业也越来越多，随之学习这块的人也变多了，音视频的开发，往往是比较难的，而这个比较难的技术就是NDK里面的技术。
* 音视频/高清大图片/人工智能/直播/抖音等等这年与用户最紧密，与我们生活最相关的技术一直都在寻找最终的技术落地平台，以前是windows系统，而现在则是移动系统了，移动系统中又是以Android占比绝大部分为前提，所以AndroidNDK技术已经是我们必备技能了。
* 要学习好NDK，其中的关于C/C++，jni，Linux基础都是需要学习的，除此之外，音视频的编解码技术，流媒体协议，ffmpeg这些都是音视频开发必备技能，而且
* OpenCV/OpenGl/这些又是图像处理必备知识，下面这些我都是当年自己搜集的资料和做的一些图，因为当年我就感觉视频这块会是一个大的趋势。所以提前做了一些准备。现在拿出来分享给大家。
**[CodeChina开源项目：《Android学习笔记总结+移动架构视频+大厂面试真题+项目实战源码》](https://codechina.csdn.net/m0_60958482/android_p7)**
ThreadLocal机制
ThreadLocal是个什么东西呢，他是个复杂的机制，毕竟从JAVA1.2就加入了机制，保证了每个线程自己的变量…
本人简单的、带有误导性的科普是：
类似一个Map，key是当前线程id，value就是你要保存的值
一定要自己深入了解该机制
Looper#loop()
这个方法也很关键，消息能够执行，起了很大作用。虽然个人感觉能看的代码很少，但是都很精炼啊。
-
获取looper，得到MQ
-
循环MQ得到可执行的msg
-
通过msg自身，去到他该去的地方
msg.target.dispatchMessage(msg);
结语
- 现在随着短视频，抖音，快手的流行NDK模块开发也显得越发重要，需要这块人才的企业也越来越多，随之学习这块的人也变多了，音视频的开发，往往是比较难的，而这个比较难的技术就是NDK里面的技术。
- 音视频/高清大图片/人工智能/直播/抖音等等这年与用户最紧密，与我们生活最相关的技术一直都在寻找最终的技术落地平台，以前是windows系统，而现在则是移动系统了，移动系统中又是以Android占比绝大部分为前提，所以AndroidNDK技术已经是我们必备技能了。
- 要学习好NDK，其中的关于C/C++，jni，Linux基础都是需要学习的，除此之外，音视频的编解码技术，流媒体协议，ffmpeg这些都是音视频开发必备技能，而且
- OpenCV/OpenGl/这些又是图像处理必备知识，下面这些我都是当年自己搜集的资料和做的一些图，因为当年我就感觉视频这块会是一个大的趋势。所以提前做了一些准备。现在拿出来分享给大家。
CodeChina开源项目：《Android学习笔记总结+移动架构视频+大厂面试真题+项目实战源码》
[外链图片转存中…(img-iOvZNkK4-1630838842626)]
