前言
关于集合中的Collection我们已经讲完了，接下来我们一起来看集合中的另一个大类：Map
Map的实现类
首先Map是一个接口，是一对键值对来存储信息的，K为key键，V为value值
HashMap
import java.util.HashMap;
import java.util.Map;
public class text1 {
public static void main(String[] args) {
/*
*增：put(K key,V value)
* 删：clear() remove(Object key)
* 改：
* 查：entrySet() get(Object key) keySet() size() values()
* 判断：containsKey(Object key) containsValue(Object value) equals(Object o) isEmpty()
*/
//创建一个Map集合，接口不可创建，需要创建他的实现类
Map<Integer,String> map = new HashMap();
map.put(1,"ymm");
map.put(2,"yxc");
map.put(5,"hh");
map.put(5,"hh");
map.put(3,"jj");
System.out.println(map.size());
System.out.println(map);
//是否包含某个值
System.out.println(map.containsKey(1));
System.out.println(map.containsValue("ymm"));
}
}
不难看出，又是无序且唯一的，是不是有点像hashset，他们俩个底层实现都是hash表实现。
像hashset和linkedhashset的关系一样，hashmap对应的linkedhashmap也可以对数据进行排序输出（加了一个链表进行维护），
LinkedHashMap实现类特点：
- 唯一
- 有序（按照输入顺序进行输出）
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
public class text1 {
public static void main(String[] args) {
LinkedHashMap<String,Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("ymm",1);
linkedHashMap.put("hh",2);
linkedHashMap.put("jj",3);
linkedHashMap.put("qq",4);
System.out.println(linkedHashMap);
}
}
HashMap原理：
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
public class text1 {
public static void main(String[] args) {
HashMap<String,Integer> hashMap = new HashMap<>();
hashMap.put("ymm",1);
hashMap.put("xxx",2);
hashMap.put("hh",4);
hashMap.put("hh",3);
System.out.println(hashMap);
System.out.println(hashMap.size());
}
}
为啥我存入4个数据但是现在size为3？
我们先弄清楚原理，再通过源码来验证。
我们在hashSet中讲过hash存储的那张图，这里涉及到hash碰撞的问题，看下图：
源码：（JDK17）
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
K，V，就对应这我们上面的String，Integer，是在创建对象之前就已经确定的，可以看出HashMap继承于AbstractMap，AbstractMap也实现了Map类接口，算是一个多余的操作。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16默认的初始化长度为16static final int MAXIMUM_CAPACITY = 1 << 30;定义了一个Max数static final float DEFAULT_LOAD_FACTOR = 0.75f;负载因子transient Node<K,V>[] table;初始数组transient int size;集合中元素的个数transient int modCount;数组扩容的边际值
那么是如何来创造出来HashMap对象的呢？
我们来看构造器：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}//1. 无参构造器
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}//2. 带参构造器- 相当于它再调用本类的构造器，传入0.75
- 带参构造器，相当于它先赋给0.75，再执行了putMapEntries方法
//putMapEntries方法
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
put方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 来自Node类：hashCode（）计算hash值
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
//^
}
//传入key和value，再调用putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; //Node类型的数组来存放
Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//初始化数组为空时候，取n为数组的初始长度
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);//传入自动计算hash值进行存放
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
//链表操作，尾插
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
//hash碰撞了
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//只替换value，不换key
afterNodeAccess(e);
//after
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}扩容resize
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}问题：
- 为什么负载因子为0.75如果负载因子为1，空间得到了很大的满足，但是会很容易产生链表，效率变低，hh。如果负载因子为0.5，碰撞概率地，扩容，空间利用变低所以取了中间值：0.75 就是时间和空间得到了折中！
- 主数组为啥要为2^n原因：
- h&(length-1)等效于h%length，这个的前提就是主数组为2^n
- 防止hash冲突
HashSet底层hh，写到这里我想笑，我们先创建一个hashset
import java.util.HashMap;
import java.util.HashSet;
public class text1 {
public static void main(String[] args) {
HashSet<Integer> hashSet = new HashSet<>();
}
}
可以看到，hashset的底层实现就是一个hashmap，相当于这俩个差不多是同一个东西
TreeMap
唯一的，有序的，我们在上篇文章中说，treeset是一个二叉树实现，TreeMap也是二叉树，那么如何用一个二叉树节点来存放俩个值呢？
颜色是指代红黑树的颜色，后面的文章再说，数字为Key，"lili"为Value
源码
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;Entry的6个属性，对应我们上面图上的6个属性
构造器：
public TreeMap() {
comparator = null;
}
/**
* Constructs a new, empty tree map, ordered according to the given
* comparator. All keys inserted into the map must be <em>mutually
* comparable</em> by the given comparator: {@code comparator.compare(k1,
* k2)} must not throw a {@code ClassCastException} for any keys
* {@code k1} and {@code k2} in the map. If the user attempts to put
* a key into the map that violates this constraint, the {@code put(Object
* key, Object value)} call will throw a
* {@code ClassCastException}.
*
* @param comparator the comparator that will be used to order this map.
* If {@code null}, the {@linkplain Comparable natural
* ordering} of the keys will be used.
*/
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}一个空构造器，一个带参构造器，我们要想传入自定义的比较类型，就只能使用带参构造器，具体实现，treeset文章中也有写到，我们这里就不具体实现了
put方法
public V put(K key, V value) {
//root为空
Entry<K,V> t = root;
if (t == null) {
//第一个元素进入
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
//封装对象
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;//将外部比较器指定
if (cpr != null) {
//进行外部比较
do {
parent = t;
cmp = cpr.compare(key, t.key);
//完全符合二叉查找树
if (cmp < 0)
//小于0，给左
t = t.left;
else if (cmp > 0)
//大于0，给右
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
标签：Map,Java,value,else,源码,key,put,hash,null
From： https://blog.51cto.com/u_15558498/6074448