写点什么

HashMap(jdk1,linux 学习路线图

用户头像
极客good
关注
发布于: 刚刚

数据结构


====


HashMap 的数据结构是? 数组 + 链表 + 红黑树(在 jdk1.8 中增加了红黑树部分)


源码分析:


=====


本文的源码是基于 jdk1.8 来分析的:


  • 与 jdk1.7 相比,jdk1.8 新增了红黑树。并不是加了红黑树效率就一定提高了,只有在链表长度不小于 8,而数组的长度不小于 64 的时候才会将链表转化为红黑树。

  • jdk1.7 的增删效率高,1.8 的增删查效率都搞。

  • jdk1.8 版本的优化在扩容机制的数组转移的地方有很巧妙设计的体现。

  • HashMap 是非线程安全的,也就是说在多线程同时对 HashMap 中的某个


【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


元素进行增删改操作的时候,是不能保证数据的一致性的。


数据结构表示


数据结构整体是数组,数组中的元素是链表节点:


存储了 hash 码,key、value、链表的指针(指向下一个节点)。


static class Node<K,V> implements Map.Entry<K,V> {


final int hash;


final K key;


V value;


Node<K,V> next;


Node(int hash, K key, V value, Node<K,V> next) {


this.hash = hash;


this.key = key;


this.value = value;


this.next = next;


}


public final K getKey() { return key; }


public final V getValue() { return value; }


public final String toString() { return key + "=" + value; }


public final int hashCode() {


return Objects.hashCode(key) ^ Objects.hashCode(value);


}


public final V setValue(V newValue) {


V oldValue = value;


value = newValue;


return oldValue;


}


public final boolean equals(Object o) {


if (o == this)


return true;


if (o instanceof Map.Entry) {


Map.Entry<?,?> e = (Map.Entry<?,?>)o;


if (Objects.equals(key, e.getKey()) &&


Objects.equals(value, e.getValue()))


return true;


}


return false;


}


}


红黑树(不详细介绍了,我自己也没有弄懂呢):


static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {


TreeNode<K,V> parent; // red-black tree links


TreeNode<K,V> left;


TreeNode<K,V> right;


TreeNode<K,V> prev; // needed to unlink next upon deletion


boolean red;


TreeNode(int hash, K key, V val, Node<K,V> next) {


super(hash, key, val, next);


}


}


介绍几个常量:


//默认数组容量大小: 16


static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16


//数组最大容量大小:2 的 30 次方


static final int MAXIMUM_CAPACITY = 1 << 30;


//默认的加载因子


static final float DEFAULT_LOAD_FACTOR = 0.75f;


//使用树而不是链表的计数阈值,将元素添加到至少这么多的节点的链表中时,链表将装换为树


static final int TREEIFY_THRESHOLD = 8;


//在哈希表扩容时,如果发现链表长度小于 6,则会由树重新退化为链表。


static final int UNTREEIFY_THRESHOLD = 6;


//可以进行树化的最小数组容量


static final int MIN_TREEIFY_CAPACITY = 64;


//存储键值对元素的数组,分配后,长度始终是 2 的幂(哈希桶数组)


transient Node<K,V>[] table;


//此映射中包含的键-值映射数,即当前数组中的元素数量


transient int size;


//主要用于记录 HashMap 内部结构发生变化的次数。


transient int modCount;


//哈希表所能容纳的最大键值对个数,下次扩容的临界值,size>=threshold 数组就会扩容


int threshold;


//负载因子


final float loadFactor;


其中 threshold = capacity * loadFactory


构造方法:


HashMap 有四个构造方法:


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);


}


public HashMap(int initialCapacity) {


this(initialCapacity, DEFAULT_LOAD_FACTOR);


}


public HashMap() {


this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted


}


public HashMap(Map<? extends K, ? extends V> m) {


this.loadFactor = DEFAULT_LOAD_FACTOR;


putMapEntries(m, false);


}


initialCapacity?初始容量

用户头像

极客good

关注

还未添加个人签名 2021.03.18 加入

还未添加个人简介

评论

发布
暂无评论
HashMap(jdk1,linux学习路线图