ArrayList
和LinkedList
都是不同步的,也就是不保证线程安全;
ArrayList
底层使用的是Object
数组;LinkedList
底层使用的是双向链表 数据结构(JDK1.6之前为循环链表,JDK1.7取消了循环。注意双向链表和双向循环链表的区别,下面有介绍到!)
ArrayList
采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。比如:执行add(E e)
方法的时候,ArrayList
会默认将指定的元素追加到此列表的末尾,这种情况的时间复杂度就是 0(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index,E e)
)时间复杂度就是 0(n - i)。因为在进行上述操作的时候,集合中第 i 个元素和第 n- i 个之后的元素都要向后/向前移一位。
② . LinkedList
采用链表存储,所以对于add(E e)
方法的插入和删除的时间复杂度不受元素位置的影响,近似 0(1),如果是要在指定位置 i 插入或删除元素的话(add(int index,E e)
)时间复杂度近似为 0(n),因为需要先移动到指定位置再插入
LinkedList
不支持搞笑的随机元素访问,而ArrayList
支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)
方法)
ArrayList
的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList
的空间花费则体现在它的每一个元素都需要消耗比 ArrayList
更多的空间(因
为要存放直接后继和直接前驱以及数据)。
RandomAccess
接口的 list,优先选择普通的 for 循环,其次是 foreachRandomAccess
接口的 list,则优先选择 iterator
遍历(foreach遍历底层也是通过 iterator实现的),大 size 的数据,千万不要使用普通for循环注:
ArrayLis
t实现了RandomAccess接口,而LinkedList
没有实现。为什么呢?我觉得还是和底层数据结构有关!ArrayList
底层是数组,而LinkedList
底层是链表。数组天然支持随机访问,时间复杂度为 O(1),所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素,时间复杂度为 O(n),所以不支持快速随机访问。ArrayList
实现了RandomAccess
接口,就表明了他具有快速随机访问功能。RandomAccess
接口只是标识,并不是说ArrayList
实现RandomAccess
接口才具有快速随机访问功能的!
更多关于 RandomAccess
接口的知识,请百度。
双向链表:包含两个指针,一个prev指向前一个节点,一个next指向后一个节点。
双向循环链表:最后一个节点的 next 指向head,而 head 的prev指向最后一个节点,构成一个环。
Vector
类的所有方法都是同步的。可以由两个线程安全地访问一个 Vector 对象,但是一个线程访问 Vector 的话代码要在同步操作上耗费大量的时间。
ArrayList
不是同步的,所以不需要保证线程安全时建议使用 ArrayList。
直接阅读Guide老哥的文章吧,我感觉写的很详细,我已经无法简写摘抄了,缺少一步都相当于缺少了灵魂:通过源码一步一步分析ArrayList 扩容机制
HashMap
是非线程安全的,HashTable
是线程安全的。HashTable
内部的方法基本都经过 synchronized
修饰。(如果要保证线程安全,就使用 ConcurrentHashMap
)
HashMap
要比 HashTable
效率高一点。另外,HashTable
基本被淘汰,不要在代码中使用它
HashMap
中,null
可以作为键,这样的键只有一个,可以有一个或多个键所对应的值为 null
。但是在HashTable
中 put 中的键值只有一个 null,直接抛出 NullPointerException
HashTable
默认的初试大小为11,之后每次扩容 ,容量变成原来的 2n+1;HashMap
默认的初试大小为 16,之后每次扩容,容量变成原来的2倍。
② . 创建时如果指定了容量初始值,那么 HashTable
会直接使用给定的大小,而 HashMap
会将其扩充为2 的幂次方大小。
HashMap
在解决 哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)时,将链表转换为红黑树,以减少搜索时间。HashTable
没有这样的机制。
HashSet
底层是基于 HashMap
实现的(HashSet
的源码非常非常少,因为除了clone()
、writeObject()
、readObject()
是 HashSet
自己不得不实现之外,其他方法都是直接调用 HashMap
中的方法。
HashMap | HashSet |
---|---|
实现了Map接口 | 实现Set接口 |
存储键值对 | 仅存储对象 |
调用put()向map中添加元素 | 调用add()方法向map中添加元素 |
HashMap使用键(Key)计算Hashcode | HashSet使用成员对象来计算hashcode值,对于两个对象来说hashcode可能相同,所以equals()方法用来判断对象的相等性 |
当把对象加入HashSet
时,HashSet
会先计算对象的HashCode
值来判断对象加入的位置,同时也会与其它加入的对象的HashCode
的值做比较,如果没有相符的HashCode
,HashSet
会假设对象没有重复出现。但是如果发现有相同的HashCode
值的对象,这时会调用equals()
方法来检查HashCode
相等的对象是否真的相同。如果两者相同,HashSet
就不会让加入操作成功。
hashcode()
与equals()
的相关规定:
== 与 equals 的区别
==
是判断两个变量或实例是不是指向同一个内存空间 ,equals
是判断两个变量或实例所指向的内存空间的值是不是相同==
是指对内存地址进行比较 equals()
是对字符串的内容进行比较==
指引用是否相同 ,equals()
指的是值是否相同JDK 1.8之前
JDK 1.8之前HashMap
底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的hashCode经过扰动函数处理后得到的 hash 值,然后通过 (n - 1)& hash 判断当前元素存放的位置(这里的n指的是数组的长度),如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash值,以及是key 是否相同,如果相同的话,直接覆盖,不相同就通过 拉链法解决冲突。
扰动函数指的就是 hashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode()
方法,换句话说使用扰动函数之后可以减少碰撞。
JDK 1.8 HashMap 的 hash 方法源码:
staticfinalinthash(Objectkey) {
int h;
// key.hashCode():返回散列值也就是hashcode
// ^ :按位异或// j>ké无符号右移,忽略符号位,空位都以0补⻬
return (keyWXnull) ?0 : (h=key.hashCode()) ^ (hj>k16);
}
JDK1.7的 HashMap 的 hash 方法源码:
staticinthash(inth) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h^= (hj>k20) ^ (hj>k12);
returnh^ (hj>k7) ^ (hj>k4);
}
JDK 1.8 的 hash方法相比于 JDK 1.7 hash 方法更加简化,但是原理不变
相比于 JDK1.8 的 hash 方法,JDK 1.7 的 hash 方法的性能会稍差一点点,因为毕竟扰动了 4 次。
“拉链法”就是:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。
JDK1.8之后相比于之前的版本, JDK1.8之后在解决哈希冲突时有了较大的变化,当链表⻓度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。
TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。
注:本块内容后期再做整理修改
为了能让 HashMap
存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀。
Hash
值 的范围值 -2147483648
到2147483647
,前后加起来大概40亿
的映射空间,只要哈希函数映射得比较均匀松散,一般应用很难出现碰撞的。但问题是一个40亿
长度的数组,内存是放不下的,所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来要存放的位置,也就是对应的数组 下标。这个数组下标的计算方法是“(n - 1)& hash
”。(n代表数组⻓度),这也就解释了HashMap
的⻓度为什么是2的幂次方。
那么,如何设计这个算法呢?
我们首先可能会想到采用%取余的操作来实现。但是,重点来了:“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%lengthdehash&(length-1)的前提是 length 是2的n 次方;)。”并且采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的⻓度为什么是2的幂次方。
主要原因在于并发下的Rehash
会造成元素之间会形成一个循环链表。不过,jdk 1.8 后解决了这个问题,但是还是不建议在多线程下使用 HashMap
,因为多线程下使用 HashMap
还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap
推荐阅读:疫苗:Java HashMap的死循环
后期补上
后期补上
后期补上
后期补上
主要根据集合的特点来选用,比如我们需要根据键值获取到元素值时就选用Map
接口下的集合,需要排序时选择TreeMap
,不需要排序时就选择HashMap
,需要保证线程安全就选用ConcurrentHashMap
.当我们只需要存放元素值时,就选择实现Collection
接口的集合,需要保证元素唯一时选择实现Set接口的集合比如TreeSet
或HashSet
,不需要就选择实现List
接口的比如ArrayList
或LinkedList
,然后再根据实现这些接口的集合的特点来选用。