1. HashMap怎么实现,为什么每次扩容都是2倍?红黑树特点,为什么不用平衡二叉树?线程安全的HashMap的实现?

实现原理:

​ 借助hash的方法,通过put和get存储和获取对象。存储对象时,我们将K/V传给put方法时,它调用hashCode计算hash从而得到bucket位置,进一步存储,HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时,我们将K传给get,它调用hashCode计算hash从而得到bucket位置,并进一步调用equals()方法确定键值对。如果发生碰撞的时候,Hashmap通过链表将产生碰撞冲突的元素组织起来,在Java 8中,如果一个bucket中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。

扩容为2倍,有两个优点:

  1. 在hashmap的源码中。put方法会调用h & (length - 1) == h % length求模,找到key对应的entry在Hash数组中的位置。如果length不为2的幂,比如15。那么length-1的2进制就会变成1110。在h为随机数的情况下,和1110做&操作。尾数永远为0(最后一位一定为0,奇数)。那么0001、1001、1101等尾数为1的位置就永远不可能被entry占用。这样会造成浪费,不随机等问题。 length-1 二进制中为1的位数越多,那么分布就平均。

  2. 另外,如果扩容是两倍话,有的Entry在hash表中的位置不变,有的位置乘以了2。元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色)
    resize

    因此,我们在扩充HashMap的时候,不需要重新计算hash,只需要看看原来的hash值新横向扩展系统(面试官问的Nginx负载均衡,说了半天才说到点上。。) 增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。

使用红黑树:

  1. AVL树是带有平衡条件的二叉搜索树。一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,左右子树树高不超过1,和红黑树相比,AVL树是严格的平衡二叉树。不管我们是执行插入还是删除操作,只要不满足平衡因子差1,就要通过旋转来保持平衡,而的树的旋转非常耗时的,由此我们可以知道AVL树适合用于插入与删除次数比较少,适合查找密集任务

    Windows NT内核中广泛存在

  2. 红黑树是一种二叉搜索树,但在每个节点增加一个存储位表示节点的颜色,可以是红或黑(非红即黑)。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍,因此,红黑树是一种弱平衡二叉树(由于是弱平衡,可以看到,在相同的节点情况下,AVL树的高度低于红黑树),相对于要求严格的AVL树来说,它的旋转次数少,所以对于搜索,插入,删除操作较多的情况下,我们就用红黑树。

为什么不用平衡二叉树?

​ 插入效率比平衡二叉树高,查询效率比普通二叉树高。所以选择性能相对折中的红黑树。

既然红黑树那么好,为啥hashmap不直接采用红黑树,而是当大于8个的时候才转换红黑树?

​ 因为红黑树需要进行左旋,右旋操作, 而单链表不需要。

​ 如果元素小于8个,查询成本高,新增成本低。如果元素大于8个,查询成本低,新增成本高。

2. 了解TreeSet吗?底层实现?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
// 使用NavigableMap的key来保存Set集合的元素
private transient NavigableMap<E,Object> m;
// 使用一个PRESENT作为Map集合的所有value
private static final Object PRESENT = new Object();

/**
*构造方法
*/
// 包访问权限的构造器,以指定的NavigableMap对象创建Set集合
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}

public TreeSet() {
// ①以自然顺序方式创建一个新的TreeMap,根据该TreeSet创建一个TreeSet
this(new TreeMap<E,Object>());
}

public TreeSet(Comparator<? super E> comparator) {
// ②以定制顺序方式创建一个新的TreeMap,根据该TreeSet创建一个TreeSet
// 使用该TreeMap的key来保存Set集合的元素
this(new TreeMap<E,Object>(comparator));
}

public TreeSet(Collection<? extends E> c) {
// 调用①号构造器创建一个TreeSet,底层以TreeMap保存集合元素
this();
// 向TreeSet中添加Collection集合c里的所有元素
addAll(c);
}

public TreeSet(SortedSet<E> s) {
// 调用②号构造器创建一个TreeSet,底层以TreeMap保存集合元素
this(s.comparator());
// 向TreeSet中添加SortedSet集合s里的所有元素
addAll(s);
}

public boolean addAll(Collection<? extends E> c) {
// Use linear-time version if applicable
if (m.size()==0 && c.size() > 0 &&
c instanceof SortedSet &&
m instanceof TreeMap) {
// 把c集合强制转换为SortedSet集合
SortedSet<? extends E> set = (SortedSet<? extends E>) c;
// 把m集合强制转换为TreeMap集合
TreeMap<E,Object> map = (TreeMap<E, Object>) m;
Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
Comparator<? super E> mc = map.comparator();
// 如果cc和mc两个Comparator相等
if (cc == mc || (cc != null && cc.equals(mc))) {
// 把Collection中所有元素添加成TreeMap集合的key
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
// 直接调用父类的addAll()方法来实现
return super.addAll(c);
}
}

3. 说一说concurranthashmap的原理

​ ConcurrentHashMap是既高效又线程安全的HashMap。

​ ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁(ReentrantLock),在ConcurrentHashMap里扮演锁的角色;HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组。Segment的结构和HashMap类似,是一种数组和链表结构。一个Segment里包含一个HashEntry数组,每个HashEntry是一个链表结构的元素,每个Segment守护着一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时,必须首先获得与它对应的Segment锁。

4. concurranthashmap和hashtable的区别

  1. HashTable容器使用synchronized来保证线程安全,但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法,其他线程也访问HashTable的同步方法时,会进入阻塞或轮询状态,因为HashTable只有一把锁。
  2. ConcurrentHashMap所使用的锁分段技术。首先将数据分成一段一段地存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。

5. 说一说你了解的红黑树

​ R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

红黑树的特性:

  1. 每个节点或者是黑色,或者是红色

  2. 根节点是黑色

  3. 每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点]

  4. 如果一个节点是红色的,则它的子节点必须是黑色的

  5. 从一个节点到String s1= “ab” + “cd”;

    String s2= “abc” + “d”; 该节点的子孙节点的所有路径上包含相同数目的黑节点

注意

  1. 特性(3)中的叶子节点,是只为空(NIL或null)的节点
  2. 特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树

6. equals与hashcode

1. equals 方法

  equals 方法来源于 Object 超类;该方法用于检测一个对象与另一个对象是否相等。

### 2. Object 中的 equals

Object 的 equals 实现如下

public boolean equals(Object obj) {
return (this == obj);
}

   由此可见,Object 中 equals 默认比较的是两个对象的内存地址(==),即默认比较两个对象的引用,引用相同返回true,反之返回false。

### 3. 重写 equals

从上面的例子可以看出,Object 中的 equals 并不适用与实际业务场景,此时我们应该 对 equals进行重写;但是 重写 equals 必须满足以下规则(特性):

  • 自反性。对于对象 x ,x.equals(x) 应当始终返回 true。

  • 对称性。对于对象 x、y,如果 x.equals(y) 返回 true,那么 y.equals(x) 也必须返回 true。

  • 传递性。对于对象 x、y、z,如果 x.equals(y) 返回 true,y.equals(z) 返回 true;那么 x.equals(z) 也必须返回 true。

  • 一致性。对于对象 x、y,如果 x.equals(y) 返回 true,那么反复调用的结果应当一直为 true。

  • 空值不等性。对于任意非空对象 x,x.equals(null) 应当永远返回 false。

    然而,对于以上5种特性,在某些特殊情况下需要严格考虑。

  • 对象属性的冲突

    假设我们将对象内的属性看作是对象内容,在实际业务场景,可能一个汽车 Car 对象 和一个人 pserson 对象具有相同的名字,比如 特斯拉;此时如果我们重写 equals 时仅仅比较对象内容的话,很可能误判为 一辆汽车和一个人相等

### 4. 重写 equals 的建议

  • 首先检测 this 与 otherObject 是否引用同一对象

    1
    if(this == otherObject) return true;
  • 然后检测 otherObject是否为 null,如果为 null 返回 false,这是必须的

    1
    if(otherObject == null) return false;
  • 其次比较 this 与 otherObject 是否同属于一个类;如果 equals 语义在子类中有所改变,则 使用 getClass 检测

    1
    if(this.getClass() != otherObject.getClass()) return false;
  • 最后将 otherObject强制转换为当前类型,并进行属性值检测;注意:如果在子类中重写的equals,则需要在重写时首先进行 super.equals(other) 判断

5. hashcode 方法

重写 equals 必须重写 hashcode,两个对象 equals 返回 true 则 hashcode 必须保证相同。

总结一下一般会有这几个问题:

  • hashcode 方法是干啥的?
  • hashcode(哈希值) 是个什么玩意?
  • hashcode 有什么用?
  • 我为啥要重写 hashcode?
  • 我不重写它有啥后果?

5.1 hashcode 方法是干啥的?

官方的解释是这样的:**hashcode 方法用于返回一个对象的哈希值。**说白了就是 hashcode 方法能返回一个 哈希值,这玩意是个整数。

5.2 hashcode(哈希值) 是个什么玩意?

由上面可知,这个 哈希值就是一个整数,可能是正数也可能是负数。

5.3 hashcode 有什么用?

hashcode(哈希值) 的作用就是用于<u>在使用 Hash算法实现的集合中确定元素位置</u>。拿我们最常见的 HashMap 来说,我们都知道 HashMap 里通过 key 取 value 时的速度 是 O(1) 级别的;

什么是 O(1)级别?

O(1)级别说白了就是 **在任意数据大小的容器中,取出一个元素所使用的时间与元素个数无关;通俗的说法就是 不论你这个 HashMap 里有100个元素还是有9999999个元素,我通过 key 取出一个元素所使用的时间是一样的。**

为何是 O(1) 级别?为何这么吊?

这个问题就要谈一下 HashMap 等 hash 容器的存储方式了;这些容器在存储元素是是这样的:首先获取你要存储元素的 hashcode(一个整数),然后再定义一个固定整数(标准叫桶数),最后用 hashcode 对 另一个整数(桶数) 取余;取余的结果即为元素要存储的下标(可能存放到数组里)。当然这里是简单的取余,可能更复杂。

当我们要从一个 HashMap 中取出一个 value 时,实际上他就是通过这套算法,用 key 的 hashcode 计算出元素位置,直接取出来了;所以说 无论你这里面有多少元素,它取的时候始终是用着一个算法、一个流程,不会因为你数据多少而产生影响,这就是 O(1) 级别的存储。

总结:由上面可知,这个 hashcode 的作用就是通过算法来确立元素存放的位置,以便于放入元素或者获取元素。

5.4 我为啥要重写 hashcode && 不重写有啥后果

  回顾一下上面:hashcode 是个整数,hashcode 方法的作用就是计算并返回这个整数;这个整数用于存放 Hash 算法实现的容器时 确定元素位置。

  接下来考虑一个业务场景:有两个对象 pserson1 和 pserson2 ,pserson1 和 pserson2 都只有两个属性,分别是名字(name)和年龄(age)。现在 pserson1 和 pserson2 的名字(name)、年龄(age) 都相同;那么我们是否可以根据业务场景来说 pserson1 和 pserson2 是同一个人

  如果说 “是” 的话,我们刚刚所认为的 “从业务角度理解 pserson1 和 pserson2 是一个人” 是不是就相当于 重写了 Pserson 的 equals 方法呢?就像下面这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Pserson {
private String name;
private int age;

// 重写 equals
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;

// 主要在这,我们根据业务逻辑,即 姓名和年龄 确立相等关系
pserson other = (pserson) obj;
if (age != other.age)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}

  我们注意到,我们根据业务逻辑重写 equals 后,造成的结果就是,两个属性相同的 Pserson 对象 我们就认为是相同的,即 equals 返回了 true; 但我们没有重写 hashcode,Object 中的 hashcode 是 native(本地的),也就是很可能不同对象返回不同的 hashcode,即使属性相同也没用。

  到这里我们再总结一下:

  • hashcode 方法返回对象的 哈希值;

    **我们通过 哈希值 的运算(与指定数取余等)来确立元素在 hash 算法实现的容器中的位置;**
  • Object 中的 hashcode 方法 对于业务逻辑上相等的两个对象(属性相同,不同引用) 返回的 hashcode 是不同的。

    墨迹了那么多最终问题来了:假设我们只重写了 pserson 的 equals 方法,使之 “属性相同即为相等”,当我们把两个 “相等的(属性相同的)” Pserson 对象 放入 HashSet 中会怎样?

    友情提示:HashSet中默认是不许放重复元素的,放重复的是会被过滤掉的

结论&&后果:当我们仅重写了 equals 保证了 “名字和年龄一样的就是一个人” 这条业务以后;把两个 pserson 对象放入 HashSet 容器里时,由于 HashSet 是通过 hashcode 来区分两个 对象存放位置,而我们又 没有根据业务逻辑重写 hashcode 方法;导致了两个 在业务上相同的对象 放到了 HashSet里,HashSet 会认为他是两个不同的对象,故最后不会去重,hashset.size()打印出来是2。

最终结论
对于重写 euqals ,要很据实际业务逻辑来,并满足上述的设计要求;一旦重写了 equals 那就必须重写 hashcode,除非你保证你的对象不会被放到 Hash 实现的容器里;不重写的话就会导致 Hash 容器认为两个属性相同的对象是2个,而不是业务上的1个。

7. 聊java基础,集合类有哪些类

序号类描述
1AbstractCollection 实现了大部分的集合接口。
2AbstractList 继承于AbstractCollection 并且实现了大部分List接口。
3AbstractSequentialList 继承于 AbstractList ,提供了对数据元素的链式访问而不是随机访问。
4LinkedList 该类实现了List接口,允许有null(空)元素。主要用于创建链表数据结构,该类没有同步方法,如果多个线程同时访问一个List,则必须自己实现访问同步,解决方法就是在创建List时候构造一个同步的List。例如:Listlist=Collections.synchronizedList(newLinkedList(...));LinkedList 查找效率低。
5ArrayList 该类也是实现了List的接口,实现了可变大小的数组,随机访问和遍历元素时,提供更好的性能。该类也是非同步的,在多线程的情况下不要使用。ArrayList 增长当前长度的50%,插入删除效率低。
6AbstractSet 继承于AbstractCollection 并且实现了大部分Set接口。
7HashSet 该类实现了Set接口,不允许出现重复元素,不保证集合中元素的顺序,允许包含值为null的元素,但最多只能一个。
8LinkedHashSet 具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现。
9TreeSet 该类实现了Set接口,可以实现排序等功能。
10AbstractMap 实现了大部分的Map接口。
11HashMap HashMap 是一个散列表,它存储的内容是键值对(key-value)映射。 该类实现了Map接口,根据键的HashCode值存储数据,具有很快的访问速度,最多允许一条记录的键为null,不支持线程同步。
12TreeMap 继承了AbstractMap,并且使用一颗树。
13WeakHashMap 继承AbstractMap类,使用弱密钥的哈希表。
14LinkedHashMap 继承于HashMap,使用元素的自然顺序对元素进行排序.
15IdentityHashMap 继承AbstractMap类,比较文档时使用引用相等。

8. 说一下hashMap底层实现原理(答1.8之前是链表+entrySet,1.8之后使用链表+红黑树)

9. hashmap的扩容机制?说一下什么叫哈希冲突

10. 聊常用算法,说一下hashmap的红黑树(大概说了一下,中间有些概念有些遗忘了,答的不太好)

11. 红黑树上的红节点主要是干什么的

场景题:十几亿个数据,实现黑白名单,标出黑名单的几个人(
答:MR 思想,
面试官:说那是离线处理,实时的呢
答:使用hashmap
面试官:十几亿数据都装到里边是不是也很大
答:使用分治的思想
面试官:倒是答到点子上了,了解过布隆过滤器么
答:听过,不了解…)

12. 说一下arraylist,默认大小,以及扩容

13. ArrayList 的初始容量根据传参确定,默认无参构造方法下新对象的容器初始大小为0。而10 是在空集合添加第一个元素时扩容时的默认容器大小

ArrayList 是如何扩容的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
* 添加元素
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

/**
* 确认集合内部容量大小
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

/**
* 计算集合的容量
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

/**
* 确认明确的容量大小
* @param minCapacity 添加元素后容器的最小容量
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

/**
* 扩容方法
* @param minCapacity 添加元素后容器的最小容量
*/
private void grow(int minCapacity) {
// 扩容前容器大小
int oldCapacity = elementData.length;
// 扩容关键算法,newCapacity 扩容后容器大小
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
// 将扩容后的容器赋值给存储容器
elementData = Arrays.copyOf(elementData, newCapacity);
}

/**
* 溢出处理
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) throw new OutOfMemoryError();
// 超过最大值不合法,直接将容量大小定义为Intager 的最大值
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
在添加元素的方法中依此调用容器大小判断相关的方法,当容器大小不够时,会进行扩容,调用grow() 方法进行扩容。扩容方法很简单,拿到扩容前容器大小old Capacity,进行扩容,判断扩容后容量是否合法,是否溢出,然后进行处理为合理的大小。

扩容算法

  扩容算法是首先获取到扩容前容器的大小。然后通过oldCapacity + (oldCapacity >> 1) 来计算扩容后的容器大小newCapacity。

  这里的扩容算法用到了>> 右移运算。即将十进制转换为二进制,每一位右移后得到的结果。oldCapacity >> 1即oldCapacity 对2 求模,oldCapacity/2;

oldCapacity + (oldCapacity >> 1)即oldCapacity + (oldCapacity / 2)

  所以关键扩容算法就是当容量不够存储元素时,在原容器大小size 基础上再扩充size 的接近一半,即大约扩充原容器的一半。

  相对直白的严谨的扩容算法如下:扩容后容器大小newCapacity = size + size / 2

14. stringbuffer和stringbuilder的区别

  1. String是字符串常量,而StringBuffer和StringBuilder是字符串变量。由String创建的字符内容是不可改变的,而由StringBuffer和StringBuidler创建的字符内容是可以改变的。

  2. StringBuffer是线程安全的,而StringBuilder是非线程安全的。StringBuilder是从JDK 5开始,为StringBuffer类补充的一个单线程的等价类。我们在使用时应优先考虑使用StringBuilder,因为它支持StringBuffer的所有操作,但是因为它不执行同步,不会有线程安全带来额外的系统消耗,所以速度更快。

    img

    img

15. String为什么不可变?

  虽然String、StringBuffer和StringBuilder都是final类,StringBuffer和StringBuilder都是继承自AbstractStringBuilder类,它们的内部实现都是靠这个父类完成的,而这个父类中定义的char数组只是一个普通是私有变量,可以用append追加。因为AbstractStringBuilder实现了Appendable接口

16. 为什么String要设计成不可变?

  1. 字符串常量池的需要

    字符串常量池(String pool, String intern pool, String保留池) 是Java堆内存中一个特殊的存储区域,当创建一个String对象时,假如此字符串值已经存在于常量池中,则不会创建一个新的对象,而是引用已经存在的对象。

    如下面的代码所示,将会在堆内存中只创建一个实际String对象.

    1
    2
    3
    String s1 = "abcd";

    String s2 = "abcd";

img

假若字符串对象允许改变,那么将会导致各种逻辑错误,比如改变一个对象会影响到另一个独立对象. 严格来说,这种常量池的思想,是一种优化手段.

思考: 假若代码如下所示,s1和s2还会指向同一个实际的String对象吗?

1
2
String s1= "ab" + "cd";
String s2= "abc" + "d";

也许这个问题违反新手的直觉, 但是考虑到现代编译器会进行常规的优化,所以他们都会指向常量池中的同一个对象。或者,你可以用 jd-gui 之类的工具查看一下编译后的class文件.

允许String对象缓存HashCode

Java中String对象的哈希码被频繁地使用, 比如在hashMap 等容器中。

字符串不变性保证了hash码的唯一性,因此可以放心地进行缓存.这也是一种性能优化手段,意味着不必每次都去计算新的哈希码. 在String类的定义中有如下代码:

``private int hash;//用来缓存HashCode``

安全性
String被许多的Java类(库)用来当做参数,例如 网络连接地址URL,文件路径path,还有反射机制所需要的String参数等, 假若String不是固定不变的,将会引起各种安全隐患。

1
2
3
4
5
6
boolean connect(string s){
if (!isSecure(s)) {
throw new SecurityException();
}
// 如果在其他地方可以修改String,那么此处就会引起各种预料不到的问题/错误causeProblem(s);
}

  总体来说, String不可变的原因包括 设计考虑,效率优化问题,以及安全性这三大方面. 事实上,这也是Java面试中的许多 “为什么” 的答案。

17. String类不可变性的好处

  1. 只有当字符串是不可变的,字符串池才有可能实现。字符串池的实现可以在运行时节约很多heap空间,因为不同的字符串变量都指向池中的同一个字符串。但如果字符串是可变的,那么String interning将不能实现(译者注:String interning是指对不同的字符串仅仅只保存一个,即不会保存多个相同的字符串。),因为这样的话,如果变量改变了它的值,那么其它指向这个值的变量的值也会一起改变。
  2. 如果字符串是可变的,那么会引起很严重的安全问题。譬如,数据库的用户名、密码都是以字符串的形式传入来获得数据库的连接,或者在socket编程中,主机名和端口都是以字符串的形式传入。因为字符串是不可变的,所以它的值是不可改变的,否则黑客们可以钻到空子,改变字符串指向的对象的值,造成安全漏洞。
  3. 因为字符串是不可变的,所以是多线程安全的,同一个字符串实例可以被多个线程共享。这样便不用因为线程安全问题而使用同步。字符串自己便是线程安全的。
  4. 类加载器要用到字符串,不可变性提供了安全性,以便正确的类被加载。譬如你想加载java.sql.Connection类,而这个值被改成了myhacked.Connection,那么会对你的数据库造成不可知的破坏。
  5. 因为字符串是不可变的,所以在它创建的时候hashcode就被缓存了,不需要重新计算。这就使得字符串很适合作为Map中的键,字符串的处理速度要快过其它的键对象。这就是HashMap中的键往往都使用字符串。

18. HashMap的实现原理

使用hash的方法,通过put和get存储和获取对象。存储对象时,我们将K/V键值对传给put方法时,它调用hashCode计算hash值从而得到bucket位置,进行存储,同时HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时,我们将K传给get,它调用hashCode计算hash从而得到bucket位置,并进一步调用equals()方法确定K/V键值对。

如果发生碰撞的时候,Hashmap通过链表将产生碰撞冲突的元素组织起来,在Java 8中,如果一个bucket中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。

19. Hash冲突

计算得到的Hash值相同,需要放到同一个bucket中

20. Hashmap插入过程

  • 对key的hashCode()做hash,然后i = (n - 1) & hash计算得到index
  • 如果节点不存在,那么创建这个节点
  • 如果节点已经存在,就替换old value(保证key的唯一性)
  • 如果碰撞了,以链表的形式存在buckets后
  • 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD),就把链表转换成红黑树
  • 如果bucket满了(超过load factor*current capacity),就要resize

21. ArrayList和LinkedList的区别

  • ArrayList是实现了基于动态数组的数据结构,而LinkedList是基于链表的数据结构;
  • 对于随机访问get和set,ArrayList要优于LinkedList,因为LinkedList要移动指针;
  • 对于添加和删除操作add和remove,一般大家都会说LinkedList要比ArrayList快,因为ArrayList要移动数据

22. Java容器可分为两大类:

  • Collection
    • List
      • ArrayList
      • LinkedList
      • Vector(了解,已过时)
    • Set
      • HashSet
        • LinkedHashSet
      • TreeSet——底层实现为TreeMap
  • Map
    • HashMap
      • LinkedHashMap
    • TreeMap——底层实现为红黑树,其实就是操作的是红黑树
    • ConcurrentHashMap
    • Hashtable(了解,,已过时)

着重标出的那些就是我们用得最多的容器。

其实,我也不知道要怎么总结好,因为之前写每一篇的时候都总结过了。现在又把他们重新罗列出来好像有点水,所以,我决定去回答一些Java容器的面试题!

当然了,我的答案未必就是正确的。如果有错误的地方大家多多包含,希望不吝在评论区留言指正~~

23. ArrayList和Vector的区别

共同点:

  • 这两个类都实现了List接口,它们都是有序的集合(存储有序),底层是数组。我们可以按位置索引号取出某个元素,允许元素重复和为null

区别:

  • 同步性:
    • ArrayList是非同步的
    • Vector是同步的
    • 即便需要同步的时候,我们可以使用Collections工具类来构建出同步的ArrayList而不用Vector
  • 扩容大小:
    • Vector增长原来的一倍,ArrayList增长原来的0.5倍

24. HashMap和Hashtable的区别

共同点:

  • 从存储结构和实现来讲基本上都是相同的,都是实现Map接口

区别:

  • 同步性:
    • HashMap是非同步的
    • Hashtable是同步的——方法上加了Synchronized
    • 需要同步的时候,我们往往不使用HashTable,而使用ConcurrentHashMap
  • 是否允许为null:
    • HashMap允许为null
    • Hashtable不允许为null
  • contains方法
    • 这知识点是在牛客网刷到的,没想到这种题还会有(我不太喜欢)….
    • Hashtable有contains方法
    • HashMap把Hashtable的contains方法去掉了,改成了containsValue和containsKey
  • 继承不同:
    • HashMap<K,V> extends AbstractMap<K,V>
    • public class Hashtable<K,V> extends Dictionary<K,V>

25. List和Map的区别

共同点:

  • 都是Java常用的容器,都是接口(ps:写出来感觉好像和没写一样…..)

不同点:

  • 存储结构不同
    • List是存储单列的集合
    • Map存储的是key-value键值对的集合
  • 元素是否可重复
    • List允许元素重复
    • Map不允许key重复
  • 是否有序
    • List集合是有序的(存储有序)
    • Map集合是无序的(存储无序)

26. Set里的元素是不能重复的,那么用什么方法来区分重复与否呢? 是用==还是equals()?

我们知道Set集合实际大都使用的是Map集合的put方法来添加元素

以HashSet为例,HashSet里的元素不能重复,在源码(HashMap)是这样体现的:

1
2
3
4
5
6
7
8
9
10
11
// 1. 如果key 相等  
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 2. 修改对应的value
if (e != null) { // existing mapping for ke y
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}

添加元素的时候,如果key(也对应的Set集合的元素)相等,那么则修改value值。而在Set集合中,value值仅仅是一个Object对象罢了(该对象对Set本身而言是无用的)。

也就是说:Set集合如果添加的元素相同时,是根本没有插入的(仅修改了一个无用的value值)!从源码(HashMap)中也看出来,==和equals()方法都有使用

27. Collection和Collections的区别

  1. Collection是集合的上级接口,继承它的有Set和List接口
  2. Collections是集合的工具类,提供了一系列的静态方法对集合的搜索、查找、同步等操作

28. 说出ArrayList,LinkedList的存储性能和特性

ArrayList的底层是数组,LinkedList的底层是双向链表

  • ArrayList它支持以角标位置进行索引出对应的元素(随机访问),而LinkedList则需要遍历整个链表来获取对应的元素。因此一般来说ArrayList的访问速度是要比LinkedList要快的
  • ArrayList由于是数组,对于删除和修改而言消耗是比较大(复制和移动数组实现),LinkedList是双向链表删除和修改只需要修改对应的指针即可,消耗是很小的。因此一般来说LinkedList的增删速度是要比ArrayList要快的

注意:

ArrayList的增删未必就是比LinkedList要慢。

  • 如果增删都是在末尾来操作【每次调用的都是remove()和add()】,此时ArrayList就不需要移动和复制数组来进行操作了。如果数据量有百万级的时,速度是会比LinkedList要快的。(我测试过)
  • 如果删除操作的位置是在中间。由于LinkedList的消耗主要是在遍历上,ArrayList的消耗主要是在移动和复制上(底层调用的是arraycopy()方法,是native方法)。
    • LinkedList的遍历速度是要慢于ArrayList的复制移动速度的
    • 如果数据量有百万级的时,还是ArrayList要快。(我测试过)

29. Enumeration和Iterator接口的区别

Iterator替代了Enumeration,Enumeration是一个旧的迭代器了。与Enumeration相比,Iterator更加安全,因为当一个集合正在被遍历的时候,它会阻止其它线程去修改集合

区别有三点:

  • Iterator的方法名比Enumeration更科学
  • Iterator有fail-fast机制,比Enumeration更安全
  • Iterator能够删除元素,Enumeration并不能删除元素

30. ListIterator有什么特点

  • ListIterator继承了Iterator接口,它用于遍历List集合的元素
  • ListIterator可以实现双向遍历,添加元素,设置元素

看一下源码的方法就知道了:

img

31. 并发集合类是什么?

Java1.5并发包(java.util.concurrent)包含线程安全集合类,允许在迭代时修改集合

  • 迭代器被设计为fail-fast的,会抛出ConcurrentModificationException。
  • 一部分类为:
    • CopyOnWriteArrayList
    • ConcurrentHashMap
    • CopyOnWriteArraySet

32. Java中HashMap的key值要是为类对象则该类需要满足什么条件?

需要同时重写该类的hashCode()方法和它的equals()方法

  • 从源码可以得知,在插入元素的时候是先算出该对象的hashCode。如果hashcode相等话的。那么表明该对象是存储在同一个位置上的。
  • 如果调用equals()方法,两个key相同,则替换元素
  • 如果调用equals()方法,两个key不相同,则说明该hashCode仅仅是碰巧相同,此时是散列冲突,将新增的元素放在桶子上

一般来说,我们会认为:只要两个对象的成员变量的值是相等的,那么我们就认为这两个对象是相等的!因为,Object底层比较的是两个对象的地址,而对我们开发来说这样的意义并不大~这也就为什么我们要重写equals()方法

重写了equals()方法,就要重写hashCode()的方法。因为equals()认定了这两个对象相同,而同一个对象调用hashCode()方法时,是应该返回相同的值的!

33. 与Java集合框架相关的有哪些最好的实践

  1. 根据需要确定集合的类型。如果是单列的集合,我们考虑用Collection下的子接口ArrayList和Set。如果是映射,我们就考虑使用Map~
  2. 确定完我们的集合类型,我们接下来确定使用该集合类型下的哪个子类~我认为可以简单分成几个步骤:
    • 是否需要同步
      • 去找线程安全的集合类使用
    • 迭代时是否需要有序(插入顺序有序)
      • 去找Linked双向列表结构的
    • 是否需要排序(自然顺序或者手动排序)
      • 去找Tree红黑树类型的(JDK1.8)
  3. 估算存放集合的数据量有多大,无论是List还是Map,它们实现动态增长,都是有性能消耗的。在初始集合的时候给出一个合理的容量会减少动态增长时的消耗~
  4. 使用泛型,避免在运行时出现ClassCastException
  5. 尽可能使用Collections工具类,或者获取只读、同步或空的集合,而非编写自己的实现。它将会提供代码重用性,它有着更好的稳定性和可维护性

34. ArrayList集合加入1万条数据,应该怎么提高效率

ArrayList的默认初始容量为10,要插入大量数据的时候需要不断扩容,而扩容是非常影响性能的。因此,现在明确了10万条数据了,我们可以直接在初始化的时候就设置ArrayList的容量

这样就可以提高效率了~

35. 说说常见的集合有哪些吧?

Map接口和Collection接口是所有集合框架的父接口:

  1. Collection接口的子接口包括:Set接口和List接口
  2. Map接口的实现类主要有:HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等
  3. Set接口的实现类主要有:HashSet、TreeSet、LinkedHashSet等
  4. List接口的实现类主要有:ArrayList、LinkedList、Stack以及Vector等

36. HashMap与HashTable的区别?

  1. HashMap没有考虑同步,是线程不安全的;Hashtable使用了synchronized关键字,是线程安全的;
  2. HashMap允许K/V都为null;后者K/V都不允许为null;
  3. HashMap继承自AbstractMap类;而Hashtable继承自Dictionary类;

37. HashMap的put方法的具体流程?

shixinzhang

答:下面先来分析一下源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
// 1.如果table为空或者长度为0,即没有元素,那么使用resize()方法扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2.计算插入存储的数组索引i,此处计算方法同 1.7 中的indexFor()方法
// 如果数组为空,即不存在Hash冲突,则直接插入数组
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 3.插入时,如果发生Hash冲突,则依次往下判断
else {
HashMap.Node<K,V> e;
K k;
// a.判断table[i]的元素的key是否与需要插入的key一样,若相同则直接用新的value覆盖掉旧的value
// 判断原则equals() - 所以需要当key的对象重写该方法
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// b.继续判断:需要插入的数据结构是红黑树还是链表
// 如果是红黑树,则直接在树中插入 or 更新键值对
else if (p instanceof HashMap.TreeNode)
e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 如果是链表,则在链表中插入 or 更新键值对
else {
// i .遍历table[i],判断key是否已存在:采用equals对比当前遍历结点的key与需要插入数据的key
// 如果存在相同的,则直接覆盖
// ii.遍历完毕后任务发现上述情况,则直接在链表尾部插入数据
// 插入完成后判断链表长度是否 > 8:若是,则把链表转换成红黑树
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 对于i情况的后续操作:发现key已存在,直接用新value覆盖旧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;
// 插入成功后,判断实际存在的键值对数量size > 最大容量
// 如果大于则进行扩容
if (++size > threshold)
resize();
// 插入成功时会调用的方法(默认实现为空)
afterNodeInsertion(evict);
return null;
}

图片简单总结为:

img

38. HashMap的扩容操作是怎么实现的?

答:通过分析源码我们知道了HashMap通过resize()方法进行扩容或者初始化的操作,下面是对源码进行的一些简单分析:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
* 该函数有2中使用情况:
1.初始化哈希表;
2.当前数组容量过小,需要扩容
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 扩容前的数组(当前数组)
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 扩容前的数组容量(数组长度)
int oldThr = threshold;
// 扩容前数组的阈值
int newCap, newThr = 0;

if (oldCap > 0) {
// 针对情况2:若扩容前的数组容量超过最大值,则不再扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 针对情况2:若没有超过最大值,就扩容为原来的2倍(左移1位)
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// double threshold
newThr = oldThr << 1;
}

// 针对情况1:初始化哈希表(采用指定或者使用默认值的方式)
else if (oldThr > 0)
// initial capacity was placed in threshold
newCap = oldThr;
else {
// zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

// 计算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每一个bucket都移动到新的bucket中去
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

39. HashMap是怎么解决哈希冲突的?

答:在解决这个问题之前,我们首先需要知道什么是哈希冲突,而在了解哈希冲突之前我们还要知道什么是哈希才行;

40. 什么是哈希?

Hash,一般翻译为“散列”,也有直接音译为“哈希”的,这就是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值(哈希值);这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

所有散列函数都有如下一个基本特性:根据同一散列函数计算出的散列值如果不同,那么输入值肯定也不同。但是,根据同一散列函数计算出的散列值如果相同,输入值不一定相同。

41. 什么是哈希冲突?

当两个不同的输入值,根据同一散列函数计算出相同的散列值的现象,我们就把它叫做碰撞(哈希碰撞)。

42. HashMap的数据结构

在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做链地址法的方式可以解决哈希冲突:

img

这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下,但相比于hashCode返回的int类型,我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4(即2的四次方16)要远小于int类型的范围,所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率,并且最坏情况下还会将HashMap变成一个单链表,所以我们还需要对hashCode作一定的优化

43. hash()函数

上面提到的问题,主要是因为如果使用hashCode取余,那么相当于参与运算的只有hashCode的低位,高位是没有起到任何作用的,所以我们的思路就是让hashCode取值出的高位也参与运算,进一步降低hash碰撞的概率,使得数据分布更平均,我们把这样的操作称为扰动,在JDK 1.8中的hash()函数如下:

1
2
3
4
5
static final int hash(Object key) {
int h;
// 与自己右移16位进行异或运算(高低位异或)
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这比在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. 引入红黑树进一步降低遍历的时间复杂度,使得遍历更快;

44. HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标?

hashCode()方法返回的是int整数类型,其范围为-(2 ^ 31)(2 ^ 31 - 1),约有40亿个映射空间,而HashMap的容量范围是在16(初始化默认值)2 ^ 30,HashMap通常情况下是取不到最大值的,并且设备上也难以提供这么多的存储空间,从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内,进而无法匹配存储位置;

面试官:那怎么解决呢?

  1. HashMap自己实现了自己的hash()方法,通过两次扰动使得它自己的哈希值高低位自行进行异或运算,降低哈希碰撞概率也使得数据分布更平均;
  2. 在保证数组长度为2的幂次方的时候,使用hash()运算之后的值与运算(&)(数组长度 - 1)来获取数组下标的方式进行存储,这样一来是比取余操作更加有效率,二来也是因为只有当数组长度为2的幂次方时,h&(length-1)才等价于h%length,三来解决了“哈希值与数组大小范围不匹配”的问题;

面试官:为什么数组长度要保证为2的幂次方呢?

  1. 只有当数组长度为2的幂次方时,h&(length-1)才等价于h%length,即实现了key的定位,2的幂次方也可以减少冲突次数,提高HashMap的查询效率
  2. 如果 length 为 2 的次幂 则 length-1 转化为二进制必定是 11111……的形式,在于 h 的二进制与操作效率会非常的快,而且空间不浪费;如果 length 不是 2 的次幂,比如 length 为 15,则 length - 1 为 14,对应的二进制为 1110,在于 h 与操作,最后一位都为 0 ,而 0001,0011,0101,1001,1011,0111,1101 这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!这样就会造成空间的浪费。

面试官:那为什么是两次扰动呢?

这样**就是加大哈希值低位的随机性**,使得分布更均匀,从而提高对应数组存储下标位置的随机性&均匀性,最终减少Hash冲突,**两次就够了,已经达到了高位低位同时参与运算的目的**;

45. HashMap在JDK1.7和JDK1.8中有哪些不同?

JDK 1.8存储结构数组 + 链表数组 + 链表 + 红黑树初始化方式单独函数:inflateTable()直接集成到了扩容函数

resize()中hash值计算方式扰动处理 = 9次扰动 = 4次位运算 + 5次异或运算扰动处理 = 2次扰动 = 1次位运算 + 1次异或运算存放数据的规则无冲突时,存放数组;

冲突时,存放链表无冲突时,存放数组;

冲突 & 链表长度 < 8:存放单链表;

冲突 & 链表长度 > 8:树化并存放红黑树插入数据方式头插法(先讲原位置的数据移到后1位,再插入数据到该位置)尾插法(直接插入到链表尾部/红黑树)扩容后存储位置的计算方式全部按照原来方法进行计算(即hashCode ->> 扰动函数 ->> (h&length-1))按照扩容后的规律计算(即扩容后的位置=原位置 or 原位置 + 旧容量)

46. 为什么HashMap中String、Integer这样的包装类适合作为K?

String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性,能够有效的减少Hash碰撞的几率

  1. 都是final类型,即不可变性,保证key的不可更改性,不会存在获取hash值不同的情况
  2. 内部已重写了equals()hashCode()等方法,遵守了HashMap内部的规范(不清楚可以去上面看看putValue的过程),不容易出现Hash值计算错误的情况;

面试官:如果我想要让自己的Object作为K应该怎么办呢?

答:重写hashCode()equals()方法

  1. 重写hashCode()是因为需要计算存储数据的存储位置,需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能,这样虽然能更快但可能会导致更多的Hash碰撞;
  2. 重写equals()方法,需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x,x.equals(null)必须返回false的这几个特性,目的是为了保证key在哈希表中的唯一性

47. ConcurrentHashMap和Hashtable的区别?

ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步,HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。

面试官:ConcurrentHashMap的具体实现知道吗?

参考资料:http://www.importnew.com/23610.html

答:在JDK1.7中,ConcurrentHashMap采用Segment + HashEntry的方式进行实现,结构如下:

img

  1. 该类包含两个静态内部类 HashEntry 和 Segment ;前者用来封装映射表的键值对,后者用来充当锁的角色;

  2. Segment 是一种可重入的锁 ReentrantLock,每个 Segment 守护一个HashEntry 数组里得元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 锁。

    JDK1.8中,放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现,结构如下:

img

插入元素过程(建议去看看源码):

  1. 如果相应位置的Node还没有初始化,则调用CAS插入相应的数据;
1
2
3
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin}
  1. 如果相应位置的Node不为空,且当前该节点不处于移动状态,则对该节点加synchronized锁,如果该节点的hash不小于0,则遍历链表更新节点或插入新节点;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value, null);
break;
}
}
}
  1. 如果该节点是TreeBin类型的节点,说明是红黑树结构,则通过putTreeVal方法往红黑树中插入节点;如果binCount不为0,说明put操作对数据产生了影响,如果当前链表的个数达到8个,则通过treeifyBin方法转化为红黑树,如果oldVal不为空,说明是一次更新操作,没有对元素个数产生影响,则直接返回旧值;
  2. 如果插入的是一个新节点,则执行addCount()方法尝试更新元素个数baseCount;

48. Java集合的快速失败机制 “fail-fast”?

是java集合的一种错误检测机制,当多个线程对集合进行结构上的改变的操作时,有可能会产生 fail-fast 机制。

例如:假设存在两个线程(线程1、线程2),线程1通过Iterator在遍历集合A中的元素,在某个时候线程2修改了集合A的结构(是结构上面的修改,而不是简单的修改集合元素的内容),那么这个时候程序就会抛出 ConcurrentModificationException 异常,从而产生fail-fast机制。

原因:迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化,就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前,都会检测modCount变量是否为expectedmodCount值,是的话就返回遍历;否则抛出异常,终止遍历。

解决办法:

1. 在遍历过程中,所有涉及到改变modCount值得地方全部加上synchronized。

2. 使用CopyOnWriteArrayList来替换ArrayList

49. ArrayList 和 Vector 的区别?

这两个类都实现了 List 接口(List 接口继承了 Collection 接口),他们都是有序集合,即存储在这两个集合中的元素位置都是有顺序的,相当于一种动态的数组,我们以后可以按位置索引来取出某个元素,并且其中的数据是允许重复的,这是与 HashSet 之类的集合的最大不同处,HashSet 之类的集合不可以按索引号去检索其中的元素,也不允许有重复的元素。

ArrayList 与 Vector 的区别主要包括两个方面:

  1. 同步性: Vector 是线程安全的,也就是说它的方法之间是线程同步(加了synchronized 关键字)的,而 ArrayList 是线程不安全的,它的方法之间是线程不同步的。如果只有一个线程会访问到集合,那最好是使用 ArrayList,因为它不考虑线程安全的问题,所以效率会高一些;如果有多个线程会访问到集合,那最好是使用 Vector,因为不需要我们自己再去考虑和编写线程安全的代码。
  2. 数据增长: ArrayList 与 Vector 都有一个初始的容量大小,当存储进它们里面的元素的个人超过了容量时,就需要增加 ArrayList 和 Vector 的存储空间,每次要增加存储空间时,不是只增加一个存储单元,而是增加多个存储单元,每次增加的存储单元的个数在内存空间利用与程序效率之间要去的一定的平衡。Vector 在数据满时(加载因子1)增长为原来的两倍(扩容增量:原容量的 2 倍),而 ArrayList 在数据量达到容量的一半时(加载因子 0.5)增长为原容量的 (0.5 倍 + 1) 个空间。

50. ArrayList和LinkedList的区别?

  1. LinkedList 实现了 List 和 Deque 接口,一般称为双向链表;ArrayList 实现了 List 接口,动态数组;
  2. LinkedList 在插入和删除数据时效率更高,ArrayList 在查找某个 index 的数据时效率更高;
  3. LinkedList 比 ArrayList 需要更多的内存;

面试官:Array 和 ArrayList 有什么区别?什么时候该应 Array 而不是 ArrayList 呢?

答:它们的区别是:

  1. Array 可以包含基本类型和对象类型,ArrayList 只能包含对象类型。
  2. Array 大小是固定的,ArrayList 的大小是动态变化的。
  3. ArrayList 提供了更多的方法和特性,比如:addAll(),removeAll(),iterator() 等等。

对于基本类型数据,集合使用自动装箱来减少编码工作量。但是,当处理固定大小的基本数据类型的时候,这种方式相对比较慢。

51. HashSet是如何保证数据不可重复的?

答:HashSet的底层其实就是HashMap,只不过我们HashSet是实现了Set接口并且把数据作为K值,而V值一直使用一个相同的虚值来保存,我们可以看到源码:

1
2
3
public boolean add(E e) {
return map.put(e, PRESENT)==null;// 调用HashMap的put方法,PRESENT是一个至始至终都相同的虚值
}

由于HashMap的K值本身就不允许重复,并且在HashMap中如果K/V相同时,会用新的V覆盖掉旧的V,然后返回旧的V,那么在HashSet中执行这一句话始终会返回一个false,导致插入失败,这样就保证了数据的不可重复性;

52. BlockingQueue是什么?

Java.util.concurrent.BlockingQueue是一个队列,在进行检索或移除一个元素的时候,它会等待队列变为非空;当在添加一个元素时,它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一部分,主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间,或消费者有可用的对象,因为它都在BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现,比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。

联系我

评论