Map Set List实现类及存储方式分析
2020-09-05 本文已影响0人
码农_薛
Map常用实现类
HashMap、LinkedHashMap、TreeMap、HashTable、ConcurrentHashMap、weakHashMap
Set 常用实现类
arraySet、hashSet、treeSet、enumSet、 linkHashSet
List常用实现类
ArrayList 、LinkedList 、Vector、Stack
Map (键值对)
1、HashMap
继承 AbstractMap 无序
使用
1）初始化
HashMap<String, String> hashMap = new HashMap<>();
2）添加数据
2）添加数据
hashMap.put("name", "张三");
3）查找数据
String name = hashMap.get("name");
4）遍历数据
for (String key : hashMap.keySet()) {
String s = hashMap.get(key);
}
存储原理
单个数据的实体类（用于保存键值对 hash 和链表信息）
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
添加数据时调用的核心代码\
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判断hashmap 数组数据是否为空
if ((tab = table) == null || (n = tab.length) == 0)
// resize 设置数组大小（默认16） 采用的<<1 增加 n表示数组的大小
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 通过(n - 1) & hash 将hash 值转换为下标 如果下标值对应的数据为空 创建并复制给i
tab[i] = newNode(hash, key, value, null);
else {
// 如果对应的下标数不为空
Node<K,V> e; K k;
//如果原始数据的key和需要添加数据的key值相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
// 如果时 TreeMap
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果hash不相同 或者key不相同 遍历P节点的链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//将新数据添加到将新数据加入P的链表中
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
//结束循环
break;
}
//如果链表中存在新数据的key值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果map中已经又同一个key的对象存在 将value替换并返回老的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
遍历时核心代码
keySet遍历时会调用 forEach方法
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
// 循环查找数据中元素
for (int i = 0; (i < tab.length && modCount == mc); ++i) {
// 循环查找链表中元素
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
存储的是 Node数组 每个Node又包含又一个链表 （put数据时并不能改变Node数组的大小）
1）通过 hash&（n-1）算出数据对应的下标
2）通过下标拿到的数据为空，将Node保存到数组中 保存流程结束。
3）如果key相同 替换对应的value 并更新 。
4）如果Key不同 则通过链表的形式保存到同一个节点中。
假如hashMap中保存了KEY为 a b c的三个数据，但是 b c 的hash值计算后的结果是一样的
保存形式为 Node数组中有两个元素时非空的 一个key 为 a的Node 另一个key 为 b或c的Node
b的next属性中保存有key为c的Node数据
核心逻辑描述
第一步首先将k,v 通过newNode()方法封装到Node对象当中。
第二步它的底层会调用K的hashCode()方法得出hash值。
第三步通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。
2、linkHashMap
LinkedHashMap继承了HashMap、有序（先后顺序）
使用
同HashMap
排序的原理
1、节点对象改为双向链表的形式
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
LinkedHashMapEntry<K,V> before, after;
}
2）重构 newNode()方法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMapEntry<K,V> p =
new LinkedHashMapEntry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
3）通过 linkNodeLast()方法将新的数据添加到链表中
// link at the end of list
private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
LinkedHashMapEntry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
3 TreeMap
继承 AbstractMap 有序（可自定义排序规则）
使用
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(10, "josan1");
treeMap.put(20, "josan2");
treeMap.put(18, "josan2");
treeMap.put(48, "josan2");
treeMap.put(8, "josan2");
for (Object key : treeMap.keySet()) {
String s = treeMap.get(key);
Log.e("日志HashMap", key.toString() + " " + s);
}
输出结果 ：
HashMap: 8 josan2
HashMap: 10 josan1
HashMap: 18 josan2
HashMap: 20 josan2
HashMap: 48 josan2
自定义排序规则
class Key extends Object implements Comparable<Key> {
int name;
public Key(int name) {
this.name = name;
}
@Override
public int compareTo(Key o) {
//先进后出
return -1;
//先进先出
return 1;
//只能保存一个数据
reture 0;
//升序
reture name-o.name;
//降序
reture o.name-name;
}
@NonNull
@Override
public String toString() {
return name+"";
}
}
private void initTreeMap() {
TreeMap<Key, String> treeMap = new TreeMap<>();
treeMap.put(new Key(10), "josan1");
treeMap.put(new Key(20), "josan2");
treeMap.put(new Key(12), "josan2");
treeMap.put(new Key(26), "josan2");
treeMap.put(new Key(20), "josan2");
for (Object key : treeMap.keySet()) {
String s = treeMap.get(key);
Log.e("日志HashMap", key.toString() + " " + s);
}
}
原理
数据实体类
static final class TreeMapEntry<K,V> implements Map.Entry<K,V> {
K key; V value;
TreeMapEntry<K,V> left;
TreeMapEntry<K,V> right;
TreeMapEntry<K,V> parent;
boolean color = BLACK;
}
put 实现源码
public V put(K key, V value) {
TreeMapEntry<K,V> t = root;
// 如果不存在根节点
if (t == null) {
// 判断是否含有比较器 如果没有报异常
compare(key, key);
// root 代表根节点
root = new TreeMapEntry<>(key, value, null);
size = 1;
modCount++;
return null;
}
// 根节点已经存在
int cmp;
TreeMapEntry<K,V> parent;
Comparator<? super K> cpr = comparator;
// 按小于0的放左边 大于0的放右边 的规则查找当前数据的父节点
if (cpr != null) {
//比较器存在
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 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;
// 如果比较器不存在 按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);
}
// 将新数据保存到父节点下方
TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
查找
final TreeMapEntry<K,V> getEntry(Object key) {
......
TreeMapEntry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
Set
HashSet
无序 不能重复
1）初始化
HashSet<String> hashSet = new HashSet<>();
2）添加数据
hashSet.add("name1");
3）查找数据
只能遍历
4）遍历数据
Iterator<String> iterator = hashSet.iterator();
while (iterator.hasNext()){ String next = iterator.next();}
原理
初始化
private transient HashMap<E,Object> map;
public HashSet() {
map = new HashMap<>();
}
添加数据
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
可以看到 HashSet 是通过HashMap来实现的
LinkHashSet 是通过LinkHashMap实现的
TreeSet 是通过TreeMap来实现的
List
ArrayList
使用 略
添加数据源码
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
查询数据源码
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
LinkedList
使用 略
数据实体类
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
添加数据
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
查询数据
public E get(int index) {
//查询index 是否符合要求
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
if (index < (size >> 1)) {
// 从第一个开始查询
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 从最后一个开始查询
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
