大家好，今天来为大家解答hashmap时间复杂度这个问题的一些问题点，包括时间复杂度和空间复杂度的概念也一样很多人还不知道，因此呢，今天就来为大家分析分析，现在让我们一起来看看吧！如果解决了您的问题，还望您关注下本站哦，谢谢~
本文目录
一、weakhashmap和hashmap的区别
1.HashMap是基于Key-Value的散列表(JDK7:数组+链表,JDK8:数组+链表+红黑树)，采用拉链法实现的。一般用于单线程当中，非线程安全，HashMap的键是"强键"。
2.继承于抽象类AbstractMap，并且实现Map接口。遍历时，取得的数据完全是随机的。
3.默认容量大小是16，加载因子是0.75。
4.最多只允许一条key为Null，允许多条value为Null。
5.HashMap实现了Cloneable和Serializable接口，而WeakHashMap没有。
1).HashMap实现Cloneable，说明它能通过clone()克隆自己。
2).HashMap实现Serializable，说明它支持序列化，能通过序列化去传输。
6.添加、删除操作时间复杂度都是O(1)。
1.weakHashMap是基于Key-Value的散列表(数组+链表)，采用拉链法实现的。一般用于单线程当中，非线程安全，weakHashMap中的键是"弱键"。
备注：当"弱键"被GC会收时，它对应的键值也会从weakHashMap中删除。
2.继承于抽象类AbstractMap，并且实现Map接口。
3.默认容量大小是16，加载因子是0.75。
4.最多只允许一条key为Null，允许多条value为Null。
二、HashMap以及其子类关键性总结
负载因子:给定默认容量为16负载因子为0.75
其实真正存放数据的是 Entry<K,V>[] table，Entry是 HashMap中的一个静态内部类，它有key、value、next、hash（key的hashcode）成员变量多个Entry就构成hashMap的数据结构数组+链表
当Hash冲突严重时,在桶上形成的链表越来越长,这样在查询时的效率就会越来越低,时间复杂度为o(N)
TREEIFY_THRESHOLD= 8用于判断是否将链表转为红黑树的阈值
当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值(默认12)---即大于当前数组的长度乘以加载因子的值的时候，就要自动扩容。
扩容(resize)就是重新计算容量,数组无法自动扩容 *** 就是使用一个新数组代替已有的容量小的数组 2倍扩容
HashMap是利用拉链法处理hashcode的碰撞问题在调用HashMap的put或者get *** 时,都会调用Hashcode *** 区查找相关的key当有冲突时在调用equals ***
HashMap基于hashing原理通过put和get *** 存取对象,当我们将键值对传递给put *** 时,他调用对象的hashCode *** 计算Hashcode知道哦啊哦哈系统位置来存储对象,当获取对象时，通过键对象的equals() *** 找到正确的键值对，然后返回值对象。
HashMap使用链表来解决碰撞问题，当碰撞发生了，对象将会存储在链表的下一个节点中。hashMap在每个链表节点存储键值对对象。当两个不同的键却有相同的hashCode时，他们会存储在同一个bucket位置的链表中。键对象的equals()来找到键值对。
ConcurrentHashMap在jdk1.7中使用了分段锁,其中segment继承于 ReentranLock,不会像HashTable那样不管是put还是get都去做同步处理,理论上ConcurrentHashMap支持CurrencyLevel(Segment数组数量)的线程并发,当每个线程占用锁访问一个Segment时,不会影响到其他的Segment
数据结构和HashMap一致数组+链表
ConcurrentHashMap里面元素存放在table数组中,分段锁就是把这个table分成多段,每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率,在ConcurrentHashMap中使用了一个包含16个锁的数组，每个锁保护所有散列桶的1/16，其中第N个散列桶由第（N mod 16）个锁来保护。假设使用合理的散列算法使关键字能够均匀的分部，那么这大约能使对锁的请求减少到越来的1/16。也正是这项技术使得ConcurrentHashMap支持多达16个并发的写入线程。
首先通过Key定位到Segment,之后再对应的Segment中具体的put元素
在1.7中已经解决了HashMap的并发问题,并且支持N个Segment这个多次数的并发,但是任然存在1.7中HashMap的问题,查询遍历链表效率低,和1.8中的HashMap结构类似,其中抛弃可原有的分段锁,采用了CAS+Synchronized来保证并发的安全
如果Obj内的Value和Expect相同就证明没有其他线程改变过这个变量,name就更新它为update如果这一步的CAS没有成功,那么就采用自选的方式继续进行CAS操作
对CAS的理解，CAS是一种无锁算法，CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做
数据结构和HashMap一致数组+链表+红黑树
1.8在 1.7的数据结构上做了大的改动，采用红黑树之后可以保证查询效率（O(logn)），甚至取消了 ReentrantLock(可重入锁)改为了 synchronized(独占锁)，这样可以看出在新版的 JDK中对 synchronized优化是很到位的。
ArrayMap利用两个数组，mHashes用来保存每一个key的hash值，mArrray大小为mHashes的2倍，依次保存key和value
当插入时，根据key的hashcode() *** 得到hash值，计算出在mArrays的index位置，然后利用二分查找找到对应的位置进行插入，当出现哈希冲突时，会在index的相邻位置插入。
SparseArray比HashMap更省内存，在某些条件下性能更好，主要是因为它避免了对key的自动装箱（int转为Integer类型），它内部则是通过两个数组来进行数据存储的，一个存储key，另外一个存储value，为了优化性能，它内部对数据还采取了压缩的方式来表示稀疏数组的数据，从而节约内存空间，我们从源码中可以看到key和value分别是用数组表示：
同时，SparseArray在存储和读取数据时候，使用的是二分查找法。也就是在put添加数据的时候，会使用二分查找法和之前的key比较当前我们添加的元素的key的大小，然后按照从小到大的顺序排列好，所以，SparseArray存储的元素都是按元素的key值从小到大排列好的。而在获取数据的时候，也是使用二分查找法判断元素的位置，所以，在获取数据的时候非常快，比HashMap快的多。
三、【老实李】JDK1.8中HashMap的红黑树
上一篇文章 HashMap的底层原理探索我们分析了JDK1.7中Hashmap的源码实现，但是在JDK1.8的时候HashMap的实现做了很大的变动和优化。1.7和1.7之前HashMap都是“数组+链表”实现的，1.8之后就是“数组+（链表或红黑树）”来实现的了。这里我特地将“链表或红黑树”用一对括号括在一起，因为HashMap底层依旧是一个数组，然后数组中的元素是链表或者红黑树来实现的。
HashMap的实现就先介绍到这，下面就先讲一下红黑树，然后才能理解为什么要用红黑树来优化HashMap，用红黑树有什么好处。
在介绍红黑树之前我们要先理解二叉查找树的数据结构。下面简单介绍一下。
上面这张图就是一个二叉查找树。二叉查找树有如下几条特性
（1）.左子树上所有结点的值均小于或等于它的根结点的值。
（2）.右子树上所有结点的值均大于或等于它的根结点的值。
（3）.左、右子树也分别为二叉排序树
那既然他名字中是有“查找”的，那么他是怎么查找的呢？比如我们要查找10这个元素，查找过程为：首先找到根节点，然后根据二叉查找树的之一二条特性，我们知道要查找的10>9所以是在根节点的右边去查找，找到13，10<13,所以接着在13的左边找，找到11,10<11,继续在11的左边查找，这样就找到了10.这其实就是二分查找的思想。最后我们要查出结果所需的更大次数就是二叉树的高度！（二分查找的思想:找到数组的中间位置的元素v，将数组分成>v和<v两部分，然后将v和要查找的数据进行一个比较，如果大于v那么就在>v的部分再次进行二分查找，否则就在<v的部分进行二分查找，直到找到对应的元素。）
那既然要查出结果所需的更大次数就是二叉树的高度，那这个高度会不会有时候很长呢？
比如我们依次插入根节点为9如下五个节点：7,6,5,4,3。依照二叉查找树的特性，结果会变成什么样呢？7,6,5,4,3一个比一个小，那么就会成一条直线，也就是成为了线性的查询，时间复杂度变成了O（N）级别。为了解决这种情况，该红黑树出场了。
红黑树其实就是一种自平衡的二叉查找树。他这个自平衡的特性就是对HashMap中链表可能会很长做出的优化。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
性质3每个叶节点（NIL节点，空节点）是黑色的。
性质4每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
下面这棵树就是一个典型的红黑树
红黑树那么多规则，那么在插入和删除元素会不会破坏红黑树的规则呢？什么情况下会破坏？什么情况下不会？
比如我们向原红黑树插入为14的新节点就不会破坏规则
向原红黑树插入值为21的新节点就破坏了规则
那么红黑树是怎么维护这个二叉查找树的自平衡性的呢？
红黑树通过“变色”和“旋转”来维护红黑树的规则，变色就是让黑的变成红的，红的变成黑的，旋转又分为“左旋转”和“右旋转”。这个比较复杂，容易晕，我们就只要知道红黑树就是通过这种方式来实现它的自平衡性就行了。
JDK1.7的时候是使用一个Entry数组来存储数据，用key的hashcode取模来决定key会被放到数组里的位置，如果hashcode相同，或者hashcode取模后的结果相同（hash collision），那么这些key会被定位到Entry数组的同一个格子里，这些key会形成一个链表。在hashcode特别差的情况下，比方说所有key的hashcode都相同，这个链表可能会很长，那么put/get操作都可能需要遍历这个链表。也就是说时间复杂度在最差情况下会退化到O(n)
红黑树我们大致了解了，他的好处就是他的自平衡性，让他这棵树的更大高度为2log(n+1)，n是树的节点数。那么红黑树的复杂度就只有 O(log n)。
下面我们通过追踪JDK1.8 HashMap的put *** 的源码来理解
通过putVal *** 可以看到这里的数组和1.7不同，是使用了一个Node数组来存储数据。那这个Node和1.7里面的Entry的区别是什么呢？
HashMap中的红黑树节点采用的是TreeNode类
TreeNode和Entry都是Node的子类，也就说Node可能是链表结构，也可能是红黑树结构。
如果插入的key的hashcode相同，那么这些key也会被定位到Node数组的同一个格子里。如果同一个格子里的key不超过8个，使用链表结构存储。如果超过了8个，那么会调用treeifyBin函数，将链表转换为红黑树。
好了，本文到此结束，如果可以帮助到大家，还望关注本站哦！
