定义map数组_Java从Map到HashMap的⼀步步实现，看这篇
⾜矣了！
点击上⽅“服务端思维”，选择“设为星标”
回复”669“获取独家整理的精选资料集
回复”加“加⼊全国服务端⾼端社「后端圈」
⼀、 Map
1.1 Map 接⼝
在 Java 中, Map 提供了键——值的映射关系。映射不能包含重复的键，并且每个键只能映射到⼀个值。
以 Map 键——值映射为基础，java.util 提供了 HashMap(最常⽤)、 TreeMap、Hashtble、LinkedHashMap 等数据结构。
衍⽣的⼏种 Map 的主要特点：
HashMap：最常⽤的数据结构。键和值之间通过 Hash函数 来实现映射关系。当进⾏遍历的 key 是⽆序的
TreeMap：使⽤红⿊树构建的数据结构，因为红⿊树的原理，可以很⾃然的对 key 进⾏排序，所以 TreeMap 的 key 遍历时是默认按照⾃然顺序(升序)排列的。
LinkedHashMap: 保存了插⼊的顺序。遍历得到的记录是按照插⼊顺序的。
1.2 Hash 散列函数
Hash (散列函数)是把任意长度的输⼊通过散列算法变换成固定长度的输出。Hash 函数的返回值也称为 哈希值 哈希码 摘要或哈希。Hash 作⽤如下图所⽰:
Hash 函数可以通过选取适当的函数，可以在时间和空间上取得较好平衡。
解决 Hash 的两种⽅式：拉链法和线性探测法
1.3 键值关系的实现
interface Entry
在 HashMap 中基于链表的实现
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
< = next;
}
⽤树的⽅式实现：
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent;  // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev;    // needed to unlink next upon deletion
boolean red;java定义一维数组并赋值
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
1.4 Map 约定的 API
1.4.1 Map 中约定的基础 API
基础的增删改查：
int size();  // 返回⼤⼩
boolean isEmpty(); // 是否为空
boolean containsKey(Object key); // 是否包含某个键
boolean containsValue(Object value); // 是否包含某个值
V get(Object key); // 获取某个键对应的值
V put(K key, V value); // 存⼊的数据
V remove(Object key); // 移除某个键
void putAll(Map extends K, ? extends V> m); //将将另⼀个集插⼊该集合中
void clear();  // 清除
Set keySet(); //获取 Map的所有的键返回为 Set集合
Collection values(); //将所有的值返回为 Collection 集合
Set> entrySet(); // 将键值对映射为 Map.Entry，内部类 Entry 实现了映射关系的实现。并且返回所有键值映射为 Set 集合。boolean equals(Object o);
int hashCode(); // 返回 Hash 值
default boolean replace(K key, V oldValue, V newValue); // 替代操作
default V replace(K key, V value);
1.4.2 Map 约定的较为⾼级的 API
default V getOrDefault(Object key, V defaultValue); //当获取失败时，⽤ defaultValue 替代。
default void forEach(BiConsumer super K, ? super V> action)  // 可⽤ lambda 表达式进⾏更快捷的遍历
default void replaceAll(BiFunction super K, ? super V, ? extends V> function);
default V putIfAbsent(K key, V value);
default V computeIfAbsent(K key,
Function super K, ? extends V> mappingFunction);
default V computeIfPresent(K key,
BiFunction super K, ? super V, ? extends V> remappingFunction);
default V compute(K key,
BiFunction super K, ? super V, ? extends V> remappingFunction)
default V merge(K key, V value,
BiFunction super V, ? super V, ? extends V> remappingFunction)
1.4.3 Map ⾼级 API 的使⽤
getOrDefault() 当这个通过 key获取值，对应的 key 或者值不存在时返回默认值，避免在使⽤过程中 null 出现，避免程序异常。
ForEach() 传⼊ BiConsumer 函数式接⼝，表达的含义其实和 Consumer ⼀样，都 accept 拥有⽅法，只是 BiConsumer 多了⼀个andThen() ⽅法，接收⼀个BiConsumer接⼝，先执⾏本接⼝的，再执⾏传⼊的参数的 accept ⽅法。
Map map = new HashMap<>();
map.put("a", "1");
map.put("b", "2");
map.put("c", "3");
map.put("d", "4");
map.forEach((k, v) -> {
System.out.println(k+"-"+v);
});
}
1.5 从 Map ⾛向 HashMap
HashMap 是 Map的⼀个实现类，也是 Map 最常⽤的实现类。
1.5.1 HashMap 的继承关系
public class HashMap extends AbstractMap
implements Map, Cloneable, Serializable
在 HashMap 的实现过程中，解决 Hash冲突的⽅法是拉链法。因此从原理来说 HashMap 的实现就是
数组 + 链表(数组保存链表的⼊⼝)。当链表过长，为了优化查询速率，HashMap 将链表转化为红⿊树(数组保存树的根节点)，使得查询速率为 log(n)，⽽不是链表的
O(n)。
⼆、HashMap
/*
* @author  Doug Lea
* @author  Josh Bloch
* @author  Arthur van Hoff
* @author  Neal Gafter
* @see    Object#hashCode()
* @see    Collection
* @see    Map
* @see    TreeMap
* @see    Hashtable
* @since  1.2
*/
⾸先 HashMap 由 Doug Lea 和 Josh Bloch 两位⼤师的参与。同时 Java 的 Collections 集合体系，并发框架 Doug Lea 也做出了不少贡献。
2.1 基本原理
对于⼀个插⼊操作，⾸先将键通过 Hash 函数转化为数组的下标。若该数组为空，直接创建节点放⼊数组中。若该数组下标存在节点，即Hash 冲突，使⽤拉链法，⽣成⼀个链表插⼊。
如果存在 Hash 冲突，使⽤拉链法插⼊，我们可以在这个链表的头部插⼊，也可以在链表的尾部插⼊，所以在 JDK 1.7 中使⽤了头部插⼊的⽅法，JDK 1.8 后续的版本中使⽤尾插法。JDK 1.7 使⽤头部插⼊的可能依据是最近插⼊的数据是最常⽤的，但是头插法带来的问题之⼀，在多线程会链表的复制会出现死循环。所以 JDK 1.8 之后采⽤的尾部插⼊的⽅法。
在 HashMap 中，前⾯说到的 数组+链表 的数组的定义
transient Node[] table;
链表的定义：
static class Node implements Map.Entry
2.1.2 提供的构造函数
public HashMap() { // 空参
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) { //带有初始⼤⼩的，⼀般情况下，我们需要规划好 HashMap 使⽤的⼤⼩，因为对于⼀次扩容操作，代价是⾮常的⼤的        this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor); // 可以⾃定义负载因⼦
三个构造函数，都没有完全的初始化 HashMap，当我们第⼀次插⼊数据时，才进⾏堆内存的分配，这样提⾼了代码的响应速度。
2.2 HashMap 中的 Hash函数定义
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 将 h ⾼ 16 位和低 16 位进⾏异或操作。
}
// 采⽤异或的原因：两个进⾏位运算，在与或异或中只有异或到的 0 和 1 的概率是相同的，⽽&和|都会使得结果偏向0或者1。
这⾥可以看到，Map 的键可以为 null，且 hash 是⼀个特定的值 0。
Hash 的⽬的是获取数组 table 的下标。Hash 函数的⽬标就是将数据均匀的分布在 table 中。
让我们先看看如何通过 hash 值得到对应的数组下标。第⼀种⽅法：hash%table.length()。但是除法操作在 CPU 中执⾏⽐加法、减法、乘法慢的多，效率低下。第⼆种⽅法 table[(table.length - 1) & hash] ⼀个与操作⼀个减法，仍然⽐除法快。这⾥的约束条件为
table.length = 2N。
table.length =16
table.length -1 = 15 1111 1111
任何⼀个数与之与操作，获取到这个数的低 8 位，其他位为 0
上⾯的例⼦可以让我们获取到对应的下标,⽽ (h = key.hashCode()) ^ (h >>> 16) 让⾼ 16 也参与运算，
让数据充分利⽤，⼀般情况下 table 的索引不会超过 216，所以⾼位的信息我们就直接抛弃了，^ (h >>> 16) 让我们在数据量较少的情况下，也可以使⽤⾼位的信息。如果
table 的索引超过 216， hashCode() 的⾼ 16 为 和 16 个 0 做异或得到的 Hash 也是公平的。
2.3 HashMap 的插⼊操作
上⾯我们已经知道如果通过 Hash 获取到 对应的 table 下标，因此我们将对应的节点加⼊到链表就完成了⼀个 Map 的映射，的确 JDK1.7中的 HashMap 实现就是这样。让我们看⼀看 JDK 为实现现实的 put 操作。
定位到 put() 操作。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
可以看到 put 操作交给了 putVal 来进⾏通⽤的实现。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict);
//onlyIfAbsent  如果当前位置已存在⼀个值，是否替换，false是替换，true是不替换
evict // 钩⼦函数的参数，LinkedHashMap 中使⽤到，HashMap 中⽆意义。
2.3.1 putVal 的流程分析
其实 putVal() 流程的函数⾮常的明了。这⾥挑了⼏个关键步骤来引导。
是否第⼀次插⼊，true 调⽤ resizer() 进⾏调整，其实此时 resizer() 是进⾏完整的初始化，之后直接赋值给对应索引的位置。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。