潍坊恒信建设集团网站,哈尔滨seo优化排名,网站分类表,wordpress的弊端Collection接口
List接口
迭代器 Iterator 是什么#xff1f;
Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来获取迭
代器实例。迭代器取代了 Java 集合框架中的 Enumeration#xff0c;迭代器允许调用者在迭代过程中移…Collection接口
List接口
迭代器 Iterator 是什么
Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来获取迭
代器实例。迭代器取代了 Java 集合框架中的 Enumeration迭代器允许调用者在迭代过程中移除元
素。
Iterator 怎么使用有什么特点
Iterator 使用代码如下
Iterator 的特点是只能单向遍历但是更加安全因为它可以确保在当前遍历
的集合元素被更改的时候就会抛出 ConcurrentModificationException 异常。
如何边遍历边移除 Collection 中的元素
边遍历边修改 Collection 的唯一正确方式是使用 Iterator.remove() 方法如下
一种 常见的错误代码如下
ListString list new ArrayList();
list. add(x);
CollectionString clist Collections. unmodifiableCollection(list);
clist. add(y); // 运行时此行报错
System. out. println(list. size());
1 ListString list new ArrayList
2 IteratorString it list. iterator
3 while(it. hasNext()){
4 String obj it. next();
5 System. out. println(obj);
6 }
1 IteratorInteger it list.iterator();
2 while(it.hasNext()){
3 *// do something*
4 it.remove();5 }
1 for(Integer i : list){
2 list.remove(i)
3 }运行以上错误代码会报 ConcurrentModificationException 异常。这是因为当使用 foreach(for(Integer
i : list)) 语句时会自动生成一个iterator 来遍历该 list但同时该 list 正在被 Iterator.remove() 修改。
Java 一般不允许一个线程在遍历 Collection 时另一个线程修改它。
Iterator 和 ListIterator 有什么区别
Iterator 可以遍历 Set 和 List 集合而 ListIterator 只能遍历 List。
Iterator 只能单向遍历而 ListIterator 可以双向遍历向前/后遍历。
ListIterator 实现 Iterator 接口然后添加了一些额外的功能比如添加一个元 素、替换一个元
素、获取前面或后面元素的索引位置。
遍历一个 List 有哪些不同的方式每种方法的实现原理是什 么Java 中 List 遍历
的最佳实践是什么
遍历方式有以下几种
1. for 循环遍历基于计数器。在集合外部维护一个计数器然后依次读 取每一个位置的元素当读
取到后一个元素后停止。
2. 迭代器遍历Iterator。Iterator 是面向对象的一个设计模式目的是屏 蔽不同数据集合的特点
统一遍历集合的接口。Java 在 Collections 中支 持了 Iterator 模式。
3. foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现使 用时不需要显式声明
Iterator 或计数器。优点是代码简洁不易出错缺 点是只能做简单的遍历不能在遍历过程中操
作数据集合例如删除、替 换。
最佳实践Java Collections 框架中提供了一个 RandomAccess 接口用来标 记 List 实现是否支持
Random Access。
如果一个数据集合实现了该接口就意味着它支持 Random Access按位置读 取元素的平均时间
复杂度为 O(1)如ArrayList。
如果没有实现该接口表示不支持 Random Access如LinkedList。 推荐的做法就是支持
Random Access 的列表可用 for 循环遍历否则建议 用 Iterator 或 foreach 遍历。
说一下 ArrayList 的优缺点
ArrayList的优点如下
ArrayList 底层以数组实现是一种随机访问模式。ArrayList 实现了 RandomAccess 接口因此查
找的时候非常快。
ArrayList 在顺序添加一个元素的时候非常方便。
ArrayList 的缺点如下
删除元素的时候需要做一次元素复制操作。如果要复制的元素很多那么就会比较耗费性能。
插入元素的时候也需要做一次元素复制操作缺点同上。
ArrayList 比较适合顺序添加、随机访问的场景。
如何实现数组和 List 之间的转换
数组转 List使用 Arrays. asList(array) 进行转换。
List 转数组使用 List 自带的 toArray() 方法。代码示例ArrayList 和 LinkedList 的区别是什么
数据结构实现ArrayList 是动态数组的数据结构实现而 LinkedList 是双向链表的数据结构实
现。
随机访问效率ArrayList 比 LinkedList 在随机访问的时候效率要高因为 LinkedList 是线性的数
据存储方式所以需要移动指针从前往后依次查找。
增加和删除效率在非首尾的增加和删除操作LinkedList 要比 ArrayList 效率要高因为
ArrayList 增删操作要影响数组内的其他数据的下标。
内存空间占用LinkedList 比 ArrayList 更占内存因为 LinkedList 的节点除了存储数据还存储
了两个引用一个指向前一个元素一个指向后一个元素。
线程安全ArrayList 和 LinkedList 都是不同步的也就是不保证线程安全
综合来说在需要频繁读取集合中的元素时更推荐使用 ArrayList而在插入和删除操作较多时更推
荐使用 LinkedList。
补充数据结构基础之双向链表
双向链表也叫双链表是链表的一种它的每个数据结点中都有两个指针分别指向直接后继和直接前
驱。所以从双向链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。
ArrayList 和 Vector 的区别是什么
这两个类都实现了 List 接口List 接口继承了 Collection 接口他们都是有序集合
ArrayList 是非线程安全的。
性能ArrayList 在性能方面要优于 Vector。
扩容ArrayList 和 Vector 都会根据实际的需要动态的调整容量只不过在
Vector 扩容每次会增加 1 倍而 ArrayList 只会增加 50%。
Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对
象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。
Arraylist不是同步的所以在不需要保证线程安全时时建议使用Arraylist。
插入数据时ArrayList、LinkedList、Vector谁速度较快阐述 ArrayList、
Vector、LinkedList 的存储性能和特性
ArrayList、LinkedList、Vector 底层的实现都是使用数组方式存储数据。数组
元素数大于实际存储的数据以便增加和插入元素它们都允许直接按序号索引元素但是插入元素要涉
及数组元素移动等内存操作所以索引数据快而插入数据慢。
Vector 中的方法由于加了 synchronized 修饰因此 Vector是线程安全容器但性能上较ArrayList差。
1 // list to array
2 ListString list new ArrayListString();
3 list.add(123);
4 list.add(456);
5 list.toArray();
6
7 // array to list
8 String[] array new String[]{123,456};
9 Arrays.asList(array);
线程安全Vector 使用了 Synchronized 来实现线程同步是线程安全的而LinkedList 使用双向链表实现存储按序号索引数据需要进行前向或后向遍历但插入数据时只需要记
录当前项的前后项即可所以 LinkedList插入速度较快。
多线程场景下如何使用 ArrayList
ArrayList 不是线程安全的如果遇到多线程场景可以通过 Collections 的
synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样
为什么 ArrayList 的 elementData 加上 transient 修饰 ArrayList 中的数组定
义如下
再看一下 ArrayList 的定义
可以看到 ArrayList 实现了 Serializable 接口这意味着 ArrayList 支持序列
化。transient 的作用是说不希望 elementData 数组被序列化重写了 writeObject 实现
每次序列化时先调用 defaultWriteObject() 方法序列化 ArrayList 中的非transient 元素然后遍历
elementData只序列化已存入的元素这样既加快了序列化的速度又减小了序列化之后的文件大
小。
List 和 Set 的区别
List , Set 都是继承自Collection 接口
List 特点一个有序元素存入集合的顺序和取出的顺序一致容器元素可以重复可以插入多个null
元素元素都有索引。常用的实现类有 ArrayList、
1 ListString synchronizedList Collections.synchronizedList(list);
2 synchronizedList.add(aaa);
3 synchronizedList.add(bbb);
4
5 for (int i 0; i synchronizedList.size(); i) {
6 System.out.println(synchronizedList.get(i));
7 }
1 private transient Object[] elementData;
1 public class ArrayListE extends AbstractListE
2 implements ListE, RandomAccess, Cloneable, java.io.Serializable
1 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOE
xception{
2 *// Write out element count, and any hidden stuff*
3 int expectedModCount modCount;
4 s.defaultWriteObject();
5 *// Write out array length*
6 s.writeInt(elementData.length);
7 *// Write out all elements in the proper order.*
8 for (int i0; isize; i)
9 s.writeObject(elementData[i]);
10 if (modCount ! expectedModCount) {
11 throw new ConcurrentModificationException();
12 }LinkedList 和 Vector。
Set 特点一个无序存入和取出顺序有可能不一致容器不可以存储重复元素只允许存入一个null
元素必须保证元素唯一性。Set 接口常用实现类是
HashSet、LinkedHashSet 以及 TreeSet。
另外 List 支持for循环也就是通过下标来遍历也可以用迭代器但是set只能用迭代因为他无序
无法用下标来取得想要的值。
Set和List对比
Set检索元素效率低下删除和插入效率高插入和删除不会引起元素位置改变。
List和数组类似List可以动态增长查找元素效率高插入删除元素效率低因为会引起其他元素位
置改变
Set接口
说一下 HashSet 的实现原理
HashSet 是基于 HashMap 实现的HashSet的值存放于HashMap的key上HashMap的value统一为
PRESENT因此 HashSet 的实现比较简单相关 HashSet 的操作基本上都是直接调用底层
HashMap 的相关方法来完成HashSet 不允许重复的值。
HashSet如何检查重复HashSet是如何保证数据不可重复的
向HashSet 中add ()元素时判断元素是否存在的依据不仅要比较hash值同时还要结合equles 方法
比较。
HashSet 中的add ()方法会使用HashMap 的put()方法。
HashMap 的 key 是唯一的由源码可以看出 HashSet 添加进去的值就是作为 HashMap 的key并且
在HashMap中如果K/V相同时会用新的V覆盖掉旧的V然后返回旧的V。所以不会重复 HashMap
比较key是否相等是先比较 hashcode 再比较equals 。
以下是HashSet 部分源码
hashCode与equals的相关规定
1. 如果两个对象相等则hashcode一定也是相同的
2. 两个对象相等,对两个equals方法返回true
3. 两个对象有相同的hashcode值它们也不一定是相等的
4. 综上equals方法被覆盖过则hashCode方法也必须被覆盖
5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()则该class的两个
对象无论如何都不会相等即使这两个对象指向相同的数据。
1 private static final Object PRESENT new Object();
2 private transient HashMapE,Object map;
3
4 public HashSet() { 5 map new HashMap ();
6 }
7
8 public boolean add(E e) {
9 // 调用HashMap的put方法,PRESENT是一个至始至终都相同的虚值
10 return map.put(e, PRESENT)null;
11 }HashMap
HashSet
实现了Map接口
实现了Set接口
存储键值对
仅存储对象
调用 put向 map中
添加元素
调用 add 方法向Set 中添加元素
HashMap 使用键
Key计算 Hashcode
HashSet 使用成员对象来计 算 hashcode 值对于两个对象 来说
hashcode 可能相 同所以 equals()方法用来判断对象的相等性如
果两个对象不同的话那 么返回 false
HashMap 相对于
HashSet 较快因为它
是使用唯一的键获取对
象
HashSet 较 HashMap 来说比较慢
与equals的区别
1. 是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存
空间的值是不是相同
2. 是指对内存地址进行比较 equals()是对字符串的内容进行比较3. 指引用是否相同 equals()指的
是值是否相同
HashSet与HashMap的区别
Queue
BlockingQueue是什么
Java.util.concurrent.BlockingQueue是一个队列在进行检索或移除一个元素的时候它会等待队列变
为非空当在添加一个元素时它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一
部分主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间或消费者有可用的
对象因为它都在BlockingQueue的实现类中被处理了。Java提供了集中 BlockingQueue的实现比如
ArrayBlockingQueue、
LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。在 Queue 中 poll()和
remove()有什么区别
相同点都是返回第一个元素并在队列中删除返回的对象。
不同点如果没有元素 poll()会返回 null而 remove()会直接抛出 NoSuchElementException 异
常。
代码示例
Map接口
1 QueueString queue new LinkedListString();
2 queue. offer(string); // add
3 System. out. println(queue. poll());
4 System. out. println(queue. remove());
5 System. out. println(queue. size());说一下 HashMap 的实现原理
HashMap概述 HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作
并允许使用null值和null键。此类不保证映射的顺序特别是它不保证该顺序恒久不变。
HashMap的数据结构 在Java编程语言中 基本的结构就是两种一个是数组另外一个是模拟指针
引用所有的数据结构都可以用这两个基本结构来构造的HashMap也不例外。HashMap实际上
是一个“链表散列”的数据结构即数组和链表的结合体。
HashMap 基于 Hash 算法实现的
1. 当我们往Hashmap中put元素时利用key的hashCode重新hash计算出当前对象的元素在数组中
的下标
2. 存储时如果出现hash值相同的key此时有两种情况。(1)如果key相
同则覆盖原始值(2)如果key不同出现冲突则将当前的key-value 放入链表中
3. 获取时直接找到hash值对应的下标在进一步判断key是否相同从而找到对应值。
4. 理解了以上过程就不难明白HashMap是如何解决hash冲突的问题核心就是使用了数组的存储方
式然后将冲突的key的对象放入链表中一旦发现冲突就在链表中做进一步的对比。
需要注意Jdk 1.8中对HashMap的实现做了优化当链表中的节点数据超过八个
之后该链表会转为红黑树来提高查询效率从原来的O(n)到O(logn)
HashMap在JDK1.7和JDK1.8中有哪些不同 HashMap的底层实现
在Java中保存数据有两种比较简单的数据结构数组和链表。数组的特点是寻址容易插入和删除
困难链表的特点是寻址困难但插入和删除容易所以我们将数组和链表结合在一起发挥两者各
自的优势使用一种叫做拉链法的方式可以解决哈希冲突。
JDK1.8之前
JDK1.8之前采用的是拉链法。拉链法将链表和数组相结合。也就是说创建一个链表数组数组中每一
格就是一个链表。若遇到哈希冲突则将冲突的值加到链表中即可。
JDK1.8之后
相比于之前的版本jdk1.8在解决哈希冲突时有了较大的变化当链表长度大于阈值默认为8时将
链表转化为红黑树以减少搜索时间。
JDK1.7 VS JDK1.8 比较
JDK1.8主要解决或优化了一下问题
1. resize 扩容优化
2. 引入了红黑树目的是避免单条链表过长而影响查询效率红黑树算法请参考
3. 解决了多线程死循环问题但仍是非线程安全的多线程时可能会造成数据丢失问题。不同
JDK 1.7
JDK 1.8
存储结构
数组 链表
数组 链表 红黑树
初始化方
式
单独函数 inflateTab le()
直接集成到了扩容 函数 resize()中
hash值计
算方式
扰动处理 9次扰动 4次位运算 5次异或运算
扰动处理 2次扰动 1次位运算 1次异或
运算
存放数据
的规则
无冲突 时存放 数组冲 突时
存 放链表
无冲突时存放 数组冲 突 链表 长度
8存放单 链表冲 突 链表 长度 8树
化并 存放红黑 树
插入数据
方式
头插法 先讲原 位置的数 据移到
后1 位再插 入数据到 该位置
尾插法 直接插 入到链表 尾部/红黑 树
扩容后存
储位置的
计算方式
全部按照 原来方法 进行计算 即
hashCode - 扰动 函数 -
(hlengt h-1)
按照扩容 后的规律 计算即 扩容后的 位置
原位 置 or 原位 置 旧容 量
HashMap的put方法的具体流程
当我们put的时候首先计算 key的hash值这里调用了 hash方法hash方法实际是让key.hashCode()
与key.hashCode()16进行异或操作高16bit补0一个数和0异或不变所以 hash 函数大概的作用
就是高16bit不变低16bit和高
16bit做了一个异或目的是减少碰撞。按照函数注释因为bucket数组大小是
2的幂计算下标index (table.length - 1) hash如果不做 hash 处理相当于散列生效的只有几个
低 bit 位为了减少散列的碰撞设计者综合考虑了速度、作用、质量之后使用高16bit和低16bit异或
来简单处理减少碰撞而且
JDK8中用了复杂度 Ologn的树结构来提升碰撞下的性能。
putVal方法执行流程图1 public V put(K key, V value) {
2 return putVal(hash(key), key, value, false, true);
3 }
4
5 static final int hash(Object key) {
6 int h;
7 return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
8 }
9
10 //实现Map.put和相关方法
11 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
12 boolean evict) {
13 NodeK,V[] tab; NodeK,V p; int n, i;
14 // 步骤①tab为空则创建
15 // table未初始化或者长度为0进行扩容
16 if ((tab table) null || (n tab.length) 0)
17 n (tab resize()).length;
18 // 步骤②计算index并对null做处理
19 // (n - 1) hash 确定元素存放在哪个桶中桶为空新生成结点放入桶中(此时这
个结点是放在数组中)
20 if ((p tab[i (n - 1) hash]) null)
21 tab[i] newNode(hash, key, value, null);
22 // 桶中已经存在元素
23 else {
24 NodeK,V e; K k;
25 // 步骤③节点key存在直接覆盖value
26 // 比较桶中第一个元素(数组中的结点)的hash值相等key相等
27 if (p.hash hash
28 ((k p.key) key || (key ! null key.equals(k))))
29 // 将第一个元素赋值给e用e来记录
30 e p;
31 // 步骤④判断该链为红黑树
32 // hash值不相等即key不相等为红黑树结点
33 // 如果当前元素类型为TreeNode表示为红黑树putTreeVal返回待存放的node, e可能为null
34 else if (p instanceof TreeNode)
35 // 放入树中
36 e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);
37 // 步骤⑤该链为链表
38 // 为链表结点
39 else {
40 // 在链表最末插入结点
41 for (int binCount 0; ; binCount) {
42 // 到达链表的尾部
43
44 //判断该链表尾部指针是不是空的
45 if ((e p.next) null) {
46 // 在尾部插入新结点
47 p.next newNode(hash, key, value, null);
48 //判断链表的长度是否达到转化红黑树的临界值临界值为8
49 if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st
50 //链表结构转树形结构
51 treeifyBin(tab, hash);
52 // 跳出循环
53 break;
54 }
55 // 判断链表中结点的key值与插入的元素的key值是否相等
56 if (e.hash hash
57 ((k e.key) key || (key ! null key.equals(k))))
58 // 相等跳出循环
59 break;
60 // 用于遍历桶中的链表与前面的e p.next组合可以遍历链表
61 p e;
62 }
63 }
64 //判断当前的key已经存在的情况下再来一个相同的hash值、key值时返回新来的val
ue这个值
65 if (e ! null) {
66 // 记录e的value
67 V oldValue e.value;
68 // onlyIfAbsent为false或者旧值为null
69 if (!onlyIfAbsent || oldValue null)
70 //用新值替换旧值
71 e.value value;
72 // 访问后回调
73 afterNodeAccess(e);
74 // 返回旧值
75 return oldValue;
76 }
77 }
78 // 结构性修改
79 modCount;
80 // 步骤⑥超过最大容量就扩容
81 // 实际大小大于阈值则扩容
82 if (size threshold)
83 resize();
84 // 插入后回调
85 afterNodeInsertion(evict);
86 return null;
87 }①.判断键值对数组table[i]是否为空或为null否则执行resize()进行扩容
②.根据键值key计算hash值得到插入的数组索引i如果table[i]null直接新建节点添加转向⑥如
果table[i]不为空转向③
③.判断table[i]的首个元素是否和key一样如果相同直接覆盖value否则转向
④这里的相同指的是hashCode以及equals
④.判断table[i] 是否为treeNode即table[i] 是否是红黑树如果是红黑树则直接在树中插入键值
对否则转向⑤
⑤.遍历table[i]判断链表长度是否大于8大于8的话把链表转换为红黑树在红黑树中执行插入操
作否则进行链表的插入操作遍历过程中若发现key已经存在直接覆盖value即可
⑥.插入成功后判断实际存在的键值对数量size是否超多了 大容量threshold如果超过进行扩容。
HashMap的扩容操作是怎么实现的
①.在jdk1.8中resize方法是在hashmap中的键值对大于阀值时或者初始化时就调用resize方法进行
扩容
②.每次扩展的时候都是扩展2倍
③.扩展后Node对象的位置要么在原位置要么移动到原偏移量两倍的位置。在putVal()中我们看到在
这个函数里面使用到了2次resize()方法resize()方法表示的在进行第一次初始化时会对其进行扩容或
者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进
行重新分发这也是JDK1.8版本的一个优化的地方在1.7中扩容之后需要重新去计算其Hash值根
据Hash值对其进行分发但在1.8版本中则是根据在同一个桶的位置中进行判断(e.hash oldCap)是
否为0重新进行hash分配后该元素的位置要么停留在原始位置要么移动到原始位置增加的数组大
小这个位置上
1 final NodeK,V[] resize() {
2 NodeK,V[] oldTab table;//oldTab指向hash桶数组
3 int oldCap (oldTab null) ? 0 : oldTab.length;
4 int oldThr threshold;
5 int newCap, newThr 0;
6 if (oldCap 0) {//如果oldCap不为空的话就是hash桶数组不为空
7 if (oldCap MAXIMUM_CAPACITY) {//如果大于最大容量了就赋值为整数最大的阀
值
8 threshold Integer.MAX_VALUE;
9 return oldTab;//返回
10 }//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16
11 else if ((newCap oldCap 1) MAXIMUM_CAPACITY
12 oldCap DEFAULT_INITIAL_CAPACITY)
13 newThr oldThr 1; // double threshold 双倍扩容阀值threshold
14 }
15 // 旧的容量为0但threshold大于零代表有参构造有cap传入threshold已经被初
始化成最小2的n次幂
16 // 直接将该值赋给新的容量
17 else if (oldThr 0) // initial capacity was placed in threshold
18 newCap oldThr;
19 // 无参构造创建的map给出默认容量和threshold 16, 16*0.75
20 else { // zero initial threshold signifies using defaults
21 newCap DEFAULT_INITIAL_CAPACITY;
22 newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
23 }
24 // 新的threshold 新的cap * 0.75
25 if (newThr 0) {26 float ft (float)newCap * loadFactor;
27 newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?
28 (int)ft : Integer.MAX_VALUE);
29 }
30 threshold newThr;
31 // 计算出新的数组长度后赋给当前成员变量table
32 SuppressWarnings({rawtypes,unchecked})
33 NodeK,V[] newTab (NodeK,V[])new Node[newCap];//新建hash桶数组
34 table newTab;//将新数组的值复制给旧的hash桶数组
35 // 如果原先的数组没有初始化那么resize的初始化工作到此结束否则进入扩容元素
重排逻辑使其均匀的分散
36 if (oldTab ! null) {
37 // 遍历新数组的所有桶下标
38 for (int j 0; j oldCap; j) {
39 NodeK,V e;
40 if ((e oldTab[j]) ! null) {
41 // 旧数组的桶下标赋给临时变量e并且解除旧数组中的引用否则就数组无法被GC回收
42 oldTab[j] null;
43 // 如果e.nextnull代表桶中就一个元素不存在链表或者红黑树
44 if (e.next null)
45 // 用同样的hash映射算法把该元素加入新的数组
46 newTab[e.hash (newCap - 1)] e;
47 // 如果e是TreeNode并且e.next!null那么处理树中元素的重排
48 else if (e instanceof TreeNode)
49 ((TreeNodeK,V)e).split(this, newTab, j, oldCap);
50 // e是链表的头并且e.next!null那么处理链表中元素重排
51 else { // preserve order
52 // loHead,loTail 代表扩容后不用变换下标见注1
53 NodeK,V loHead null, loTail null;
54 // hiHead,hiTail 代表扩容后变换下标见注1
55 NodeK,V hiHead null, hiTail null;
56 NodeK,V next;
57 // 遍历链表
58 do {
59 next e.next;
60 if ((e.hash oldCap) 0) {
61 if (loTail null)
62 // 初始化head指向链表当前元素ee不一定是链表的第一个元素初始化后loHead
63 // 代表下标保持不变的链表的头元素
64 loHead e;
65 else
66 // loTail.next指向当前e
67 loTail.next e;
68 // loTail指向当前的元素e
69 // 初始化后loTail和loHead指向相同的内存所以当loTail.next指向下一个元素
时
70 // 底层数组中的元素的next引用也相应发生变化造成lowHead.next.next.....
71 // 跟随loTail同步使得lowHead可以链接到所有属于该链表的元素。
72 loTail e;
73 }
74 else {
75 if (hiTail null)
76 // 初始化head指向链表当前元素e, 初始化后hiHead代表下标更改的链表头元素
77 hiHead e;
78 else
79 hiTail.next e;
80 hiTail e;
81 }HashMap是怎么解决哈希冲突的
答在解决这个问题之前我们首先需要知道什么是哈希冲突而在了解哈希冲突之前我们还要知道什
么是哈希才行什么是哈希
Hash一般翻译为“散列”也有直接音译为“哈希”的这就是把任意长度的输入通过散列算法变换成
固定长度的输出该输出就是散列值哈希值这种转换是一种压缩映射也就是散列值的空间通
常远小于输入的空间不同的输入可能会散列成相同的输出所以不可能从散列值来唯一的确定输入
值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
所有散列函数都有如下一个基本特性根据同一散列函数计算出的散列值如果不同那么输入值肯定也
不同。但是根据同一散列函数计算出的散列值如果相同输入值不一定相同。
什么是哈希冲突
当两个不同的输入值根据同一散列函数计算出相同的散列值的现象我们就把它叫做碰撞哈希碰
撞。
HashMap的数据结构
在Java中保存数据有两种比较简单的数据结构数组和链表。数组的特点是寻址容易插入和删除
困难链表的特点是寻址困难但插入和删除容易所以我们将数组和链表结合在一起发挥两者各
自的优势使用一种叫做链地址法的方式可以解决哈希冲突
82 } while ((e next) ! null);
83 // 遍历结束, 将tail指向null并把链表头放入新数组的相应下标形成新的映射。
84 if (loTail ! null) {
85 loTail.next null;
86 newTab[j] loHead;
87 }
88 if (hiTail ! null) {
89 hiTail.next null;
90 newTab[j oldCap] hiHead;
91 }
92 }
93 }
94 }
95 }
96 return newTab;
97 }这样我们就可以将拥有相同哈希值的对象(img)组织成一个链表放在hash值所对应的 bucket下但相比
于hashCode返回的int类型我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY 1 4即
2的四次方16要远小于int类型的范围所以我们如果只是单纯的用hashCode取余来获取对应的
bucket这将会大大增加哈希碰撞的概率并且最坏情况下还会将HashMap变成一个单链表所以我们还
需要对hashCode作一定的优化 hash()函数
上面提到的问题主要是因为如果使用hashCode取余那么相当于参与运算的只有hashCode的低位
高位是没有起到任何作用的所以我们的思路就是让 hashCode取值出的高位也参与运算进一步降低
hash碰撞的概率使得数据分布更平均我们把这样的操作称为扰动在JDK 1.8中的hash()函数如下
这比在JDK 1.7中更为简洁相比在1.7中的4次位运算5次异或运算
9次扰动在1.8中只进行
了1次位运算和1次异或运算
2次扰动
JDK1.8新增红黑树
通过上面的链地址法使用散列表和扰(img)动函数我们成功让我们的数据分布更平均哈希碰撞减
少但是当我们的HashMap中存在大量数据时加入我们某个 bucket下对应的链表有n个元素那么遍
历时间复杂度就为O(n)为了针对这个问题JDK1.8在HashMap中新增了红黑树的数据结构进一步使
得遍历复杂度降低至O(logn)总结
简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的
1. 使用链地址法使用散列表来链接拥有相同hash值的数据
2. 使用2次扰动函数hash函数来降低哈希冲突的概率使得数据分布更平均
3. 引入红黑树进一步降低遍历的时间复杂度使得遍历更快
1 static final int hash(Object key) {
2 int h;
3 return (key null) ? 0 : (h key.hashCode()) ^ (h 16);// 与自己右移16位
进行异或运算高低位异或
4 }能否使用任何类作为 Map 的 key
可以使用任何类作为 Map 的 key然而在使用之前需要考虑以下几点 如果类重写了 equals() 方
法也应该重写 hashCode() 方法。类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。
如果一个类没有使用 equals()不应该在 hashCode() 中使用它。
用户自定义 Key 类 佳实践是使之为不可变的这样 hashCode() 值可以被缓存起来拥有更好的性能。
不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变这样就会解决与可变相关的问题了。
为什么HashMap中String、Integer这样的包装类适合作为K
答String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性能够有效的减少
Hash碰撞的几率
1. 都是final类型即不可变性保证key的不可更改性不会存在获取 hash值不同的情况
内部已重写了equals()、hashCode()等方法遵守了HashMap内部的规范不清楚可以去上面看看
putValue的过程不容易出现Hash值计算错误的情况
如果使用Object作为HashMap的Key应该怎么办呢
答重写hashCode()和equals()方法
1. 重写hashCode()是因为需要计算存储数据的存储位置需要注意不要试图从散列码计算中排除掉一
个对象的关键部分来提高性能这样虽然能更快但可能会导致更多的Hash碰撞
2. 重写equals()方法需要遵守自反性、对称性、传递性、一致性以及对
于任何非null的引用值xx.equals(null)必须返回false的这几个特性目的是为了保证key在哈希表中的
唯一性
HashMap为什么不直接使用hashCode()处理后的哈希 值直接作为table的下标
答hashCode()方法返回的是int整数类型其范围为-(2 ^ 31)~(2 ^ 31 - 1)约有40亿个映射空间而
HashMap的容量范围是在16初始化默认值~2 ^ 30HashMap通常情况下是取不到 大值的并且
设备上也难以提供这么多的存储空间从而导致通过hashCode()计算出的哈希值可能不在数组大小范围
内进而无法匹配存储位置
那怎么解决呢
1. HashMap自己实现了自己的hash()方法通过两次扰动使得它自己的哈希值高低位自行进行异或运
算降低哈希碰撞概率也使得数据分布更平均
2. 在保证数组长度为2的幂次方的时候使用hash()运算之后的值与运算
数组长度 - 1来获取数组下标的方式进行存储这样一来是比取
余操作更加有效率二来也是因为只有当数组长度为2的幂次方时h
(length-1)才等价于h%length三来解决了“哈希值与数组大小范围不匹配的问题
HashMap 的长度为什么是2的幂次方
为了能让 HashMap 存取高效尽量较少碰撞也就是要尽量把数据分配均匀每个链表/红黑树长度大
致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。
这个算法应该如何设计呢我们首先可能会想到采用%取余的操作来实现。但是重点来了“取余(%)操
作中如果除数是2的幂次则等价于与其除数减一的与()操作也就是说
hash%lengthhash(length-1)的前提是 length 是2的 n 次方。” 并且 采用二进制位操作 相对
于%能够提高运算效率这就解释了 HashMap 的长度为什么是2的幂次方。那为什么是两次扰动呢答这样就是加大哈希值低位的随机性使得分布更均匀从而提高对应数组
存储下标位置的随机性均匀性 终减少Hash冲突两次就够了已经达到了高位低位同时参与运算
的目的
HashMap 与 HashTable 有什么区别
1. 线程安全 HashMap 是非线程安全的HashTable 是线程安全的
HashTable 内部的方法基本都经过 synchronized 修饰。如果你要保证线程安全的话就使用
ConcurrentHashMap 吧
2. 效率 因为线程安全的问题HashMap 要比 HashTable 效率高一点。另外HashTable 基本被
淘汰不要在代码中使用它
3. 对Null key 和Null value的支持 HashMap 中null 可以作为键这样的键只有一个可以有一
个或多个键所对应的值为 null。但是在
HashTable 中 put 进的键值只要有一个 null直接抛
NullPointerException。
4. 初始容量大小和每次扩充容量大小的不同 ①创建时如果不指定容量初始值Hashtable 默认的
初始大小为11之后每次扩充容量变为原来的2n1。HashMap 默认的初始化大小为16。之后
每次扩充容量变为原来的2倍。②创建时如果给定了容量初始值那么 Hashtable 会直接使用你
给定的大小而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为
哈希表的大小后面会介绍到为什么是2 的幂次方。
5. 底层数据结构 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化当链表长度大于阈
值默认为8时将链表转化为红黑树以减少搜索时间。Hashtable 没有这样的机制。
6. 推荐使用在 Hashtable 的类注释可以看到Hashtable 是保留类不建议使用推荐在单线程环境
下使用 HashMap 替代如果需要多线程使用则用 ConcurrentHashMap 替代。
如何决定使用 HashMap 还是TreeMap
对于在Map中插入、删除和定位元素这类操作HashMap是 好的选择。然
而假如你需要对一个有序的key集合进行遍历TreeMap是更好的选择。基于你的collection的大小
也许向HashMap中添加元素会更快将map换为TreeMap进行有序key的遍历
HashMap 和 ConcurrentHashMap 的区别
1. ConcurrentHashMap对整个桶数组进行了分割分段(Segment)然后在每一个分段上都用lock锁进
行保护相对于HashTable的synchronized 锁的粒度更精细了一些并发性能更好而HashMap
没有锁机制不是线程安全的。JDK1.8之后ConcurrentHashMap启了一种全新的方式实现,利用
CAS算法。
2. HashMap的键值对允许有null但是ConCurrentHashMap都不允许。
ConcurrentHashMap 和 Hashtable 的区别
ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
底层数据结构 JDK1.7的 ConcurrentHashMap 底层采用 分段的数组
链表 实现JDK1.8 采用的数据结构跟HashMap1.8的结构一样数组链表/红黑
二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组链表 的形式数组
是 HashMap 的主体链表则是主要为了解决哈希冲突而存在的
实现线程安全的方式重要 ① 在JDK1.7的时候ConcurrentHashMap分段锁 对整个桶数组进行了分割分段(Segment)每一把锁只锁容器其中一
部分数据多线程访问容器里不同数据段的数据就不会存在锁竞争提高并发访问率。默认分配16
个Segment比Hashtable效率提高16
倍。 到了 JDK1.8 的时候已经摒弃了Segment的概念而是直接用
Node 数组链表红黑树的数据结构来实现并发控制使用
synchronized 和 CAS 来操作。JDK1.6以后 对 synchronized锁做了很多优化 整个看起来就像是优
化过且线程安全的 HashMap虽然在JDK1.8中还
能看到 Segment 的数据结构但是已经简化了属性只是为了兼容旧版本②
Hashtable(同一把锁) :使用 synchronized 来保证线程安全效率非常低下。当一个线程访问同步方法
时其他线程也访问同步方法可能会进入阻塞或轮询状态如使用 put 添加元素另一个线程不能使
用 put 添加元素也不能使用 get竞争会越来越激烈效率越低。
两者的对比图
HashTable:
JDK1.7的ConcurrentHashMapJDK1.8的ConcurrentHashMapTreeBi(img)n: 红黑二叉树节点 Node: 链表节点
答ConcurrentHashMap 结合了 Hash(img)Map 和 HashTable 二者的优势。 HashMap 没有考虑同
步HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。
ConcurrentHashMap 锁的方式是稍微细粒度的。
ConcurrentHashMap 底层具体实现知道吗实现原理是什么
JDK1.7
首先将数据分为一段一段的存储然后给每一段数据配一把锁当一个线程占用锁访问其中一个段数据
时其他段的数据也能被其他线程访问。
在JDK1.7中ConcurrentHashMap采用Segment HashEntry的方式进行实
现结构如下
一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap类似是一种数
组和链表结构一个 Segment 包含一个 HashEntry 数组每个 HashEntry 是一个链表结构的元素每
个 Segment 守护着一个 HashEntry数组里的元素当对 HashEntry 数组的数据进行修改时必须首先
获得对应的 Segment的锁。1. 该类包含两个静态内部类 HashE(img)ntry 和 Segment 前者用来封装映射表的键值对后者用来
充当锁的角色
2. Segment 是一种可重入的锁 ReentrantLock每个 Segment 守护一个HashEntry 数组里得元素
当对 HashEntry 数组的数据进行修改时必须首先获得对应的 Segment 锁。
JDK1.8
在JDK1.8中放弃了Segment臃肿的设计取而代之的是采用Node CAS Synchronized来保证并发
安全进行实现synchronized只锁定当前链表或红黑二叉树的首节点这样只要hash不冲突就不会产
生并发效率又提升N 倍。
结构如下
看插入元素过程建议去看看源码
如果相应位置的Node还没有初始化则调用CAS插入相应的数据
1 else if ((f tabAt(tab, i (n - 1) hash)) null) {
2 if (casTabAt(tab, i, null, new NodeK,V(hash, key, value, null)))
3 break; // no lock when adding to empty bin
4 }
如果相应位置的Node不为空且当前该节点不处于移动状态则对该节点加
synchronized锁如果该节点的hash不小于0则遍历链表更新节点或插入新节点
1 if (fh 0) {1. 如果该节点是TreeBin类型的节点说明是红黑树结构则通过 putTreeVal方法往红黑树中插入节
点如果binCount不为0说明put操作对数据产生了影响如果当前链表的个数达到8个则通过
treeifyBin方法转化为红黑树如果oldVal不为空说明是一次更新操作没有对元素个数产生影
响则直接返回旧值
2. 如果插入的是一个新节点则执行addCount()方法尝试更新元素个数 baseCount
辅助工具类
Array 和 ArrayList 有何区别
Array 可以存储基本数据类型和对象ArrayList 只能存储对象。
Array 是指定固定大小的而 ArrayList 大小是自动扩展的。
Array 内置方法没有 ArrayList 多比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。
对于基本类型数据集合使用自动装箱来减少编码工作量。但是当处理固定大小的基本数据类型的时
候这种方式相对比较慢。
如何实现 Array 和 List 之间的转换
Array 转 List Arrays. asList(array)
List 转 ArrayList 的 toArray() 方法。
comparable 和 comparator的区别
comparable接口实际上是出自java.lang包它有一个 compareTo(Object obj)方法用来排序
comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用
来排序
一般我们需要对一个集合使用自定义排序时我们就要重写compareTo方法或 compare方法当我们
需要对某一个集合实现两种排序方式比如一个song对象中的歌名和歌手名分别采用一种排序方法的
话我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名
排序和歌星名排序第二种代表我们只能使用两个参数版的Collections.sort().
2 binCount 1;
3 for (NodeK,V e f;; binCount) {
4 K ek;
5 if (e.hash hash
6 ((ek e.key) key ||
7 (ek ! null key.equals(ek)))) {
8 oldVal e.val;
9 if (!onlyIfAbsent)
10 e.val value;
11 break;
12 }
13 NodeK,V pred e;
14 if ((e e.next) null) {
15 pred.next new NodeK,V(hash, key, value, null);
16 break;
17 }
18 }
19 }Collection 和 Collections 有什么区别
java.util.Collection 是一个集合接口集合类的一个顶级接口。它提供了对集合对象进行基本操
作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为
各种具体的集合提供了 大化的统一操作方式其直接继承接口有List与Set。
Collections则是集合类的一个工具类/帮助类其中提供了一系列静态方法用于对集合中元素进
行排序、搜索以及线程安全等各种操作。
TreeMap 和 TreeSet 在排序时如何比较元素 Collections 工具类中的 sort()方
法如何比较元素
TreeSet 要求存放的对象所属的类必须实现 Comparable 接口该接口提供了比较元素的 compareTo()
方法当插入元素时会回调该方法比较元素的大小。
TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进 行排 序。
Collections 工具类的 sort 方法有两种重载的形式
第一种要求传入的待排序容器中存放的对象比较实现 Comparable 接口以实现元素的比较
第二种不强制性的要求容器中的元素必须可比较但是要求传入第二个参数参数是Comparator 接口
的子类型需要重写 compare 方法实现元素的比较相当于一个临时定义的排序规则其实就是通
过接口注入比较元素大小的算法也是对回调模式的应用Java 中对函数式编程的支持。
Vector,ArrayList, LinkedList的区别是什么
答
1. Vector、ArrayList都是以类似数组的形式存储在内存中LinkedList则以链表的形式进行存储。
2. List中的元素有序、允许有重复的元素Set中的元素无序、不允许有重复元素。
3. Vector线程同步ArrayList、LinkedList线程不同步。
4. LinkedList适合指定位置插入、删除操作不适合查找ArrayList、Vector适合查找不适合指定
位置的插入、删除操作。
5. ArrayList在元素填满容器时会自动扩充容器大小的50%而Vector则是100%因此ArrayList更节
省空间。
HashTable, HashMapTreeMap区别
答
1. HashTable线程同步HashMap非线程同步。
2. HashTable不允许键,值有空值HashMap允许键,值有空值。
3. HashTable使用EnumerationHashMap使用Iterator。
4. HashTable中hash数组的默认大小是11增加方式的old*21HashMap中hash数组的默认大小
是16增长方式一定是2的指数倍。
5. TreeMap能够把它保存的记录根据键排序默认是按升序排序。
HashMap的数据结构
jdk1.8之前list 链表
jdk1.8之后list 链表当链表长度到8时转化为红黑树
HashMap的扩容因子默认0.75也就是会浪费1/4的空间达到扩容因子时会将list扩容一倍0.75 是时间与空间一个平衡
值
多线程修改HashMap
多线程同时写入同时执行扩容操作多线程扩容可能死锁、丢数据可以对HashMap 加入同步锁
Collections.synchronizedMap(hashMap)但是效率很低因为该锁是互斥锁同一时刻只能有一个线
程执行读写操作这时候应该使用ConcurrentHashMap
注意在使用Iterator遍历的时候LinkedHashMap会产生
java.util.ConcurrentModificationException 。
扩展HashMap增加双向链表的实现号称是最占内存的数据结构。支持iterator()时按Entry的插入
顺序来排序(但是更新不算 如果设置accessOrder属性为true则所有读写访问都算)。实现上是
在Entry上再增加属性before/after指针插入时把自己加到Header Entry的前面去。如果所有读
写访问都要排序还要把前后Entry的before/after拼接起来以在链表中删除掉自己。
