容器总结

List,Set,Map三者的区别?

  • List(对付顺序的好帮手): List接口存储一组不唯一(可以有多个元素引用相同的对象),有序的对象
  • Set(注重独一无二的性质): 不允许重复的集合。不会有多个元素引用相同的对象。
  • Map(用Key来搜索的专家): 使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象,但Key不能重复,典型的Key是String类型,但也可以是任何对象。

Arraylist 与 LinkedList 区别?

  • 1. 是否保证线程安全: ArrayListLinkedList 都是不同步的,也就是不保证线程安全;
  • 2. 底层数据结构: Arraylist 底层使用的是 Object 数组LinkedList 底层使用的是 双向链表 数据结构(JDK1.6之前为循环链表,JDK1.7取消了循环。注!意双向链表和双向循环链表的区别,下面有介绍到!)
  • 3. 插入和删除是否受元素位置的影响:ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行add(E e)方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element))时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储,所以对于add(E e)方法的插入,删除元素时间复杂度不受元素位置的影响,近似 O(1),如果是要在指定位置i插入和删除元素的话((add(int index, E element)) 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。(LinkedList数据结构记录了头节点\尾节点);remove(obj)操作是指找到元素后的删除操作时间复杂度为o(1),实际上需要先顺序寻找对象,通过equals逐个对比,进行remove
  • 4. 是否支持快速随机访问: LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
  • 5. 内存空间占用: ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间(因为要存放直接后继和直接前驱以及数据)。

在这里插入图片描述

补充内容:RandomAccess接口

1
2
public interface RandomAccess {
}

查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以,在我看来 RandomAccess 接口不过是一个标识罢了。标识什么? 标识实现这个接口的类具有随机访问功能。

binarySearch()方法中,它要判断传入的list 是否 RamdomAccess 的实例,如果是,调用indexedBinarySearch()方法,如果不是,那么调用iteratorBinarySearch()方法

1
2
3
4
5
6
7
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}

ArrayList 实现了 RandomAccess 接口, 而 LinkedList 没有实现。为什么呢?我觉得还是和底层数据结构有关!ArrayList 底层是数组,而 LinkedList 底层是链表。数组天然支持随机访问,时间复杂度为 O(1),所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素,时间复杂度为 O(n),所以不支持快速随机访问。,ArrayList 实现了 RandomAccess 接口,就表明了他具有快速随机访问功能。 RandomAccess 接口只是标识,并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的!

下面再总结一下 list 的遍历方式选择:

  • 实现了 RandomAccess 接口的list,优先选择普通 for 循环 ,其次 foreach,
  • 未实现 RandomAccess接口的list,优先选择iterator遍历(foreach遍历底层也是通过iterator实现的,),大size的数据,千万不要使用普通for循环

for,foreach,iterator的用法和区别

补充内容:双向链表和双向循环链表

双向链表: 包含两个指针,一个prev指向前一个节点,一个next指向后一个节点。

双向链表

双向循环链表: 最后一个节点的 next 指向head,而 head 的prev指向最后一个节点,构成一个环。

双向循环链表

ArrayList 与 Vector 区别呢?为什么要用Arraylist取代Vector呢?

Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。

Arraylist不是同步的,所以在不需要保证线程安全时建议使用Arraylist。

说一说 ArrayList 的扩容机制吧

详见笔主的这篇文章:通过源码一步一步分析ArrayList 扩容机制

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,之后每次扩充,容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。②创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为 2 的幂次方大小(HashMap 中的tableSizeFor()方法保证,下面给出了源代码)。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小, 后面会介绍到为什么是 2 的幂次方。
  5. 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。

HashMap 中带有初始容量的构造函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);
}

下面这个方法保证了 HashMap 总是使用 2 的幂作为哈希表的大小。

1
2
3
4
5
6
7
8
9
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1; //|= 表示或运算 0011|1100 = 1111
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

HashMap 和 HashSet 区别

如果你看过 HashSet 源码的话就应该知道:HashSet 底层就是基于 HashMap 实现的。(HashSet 的源码非常非常少,因为除了 clone()writeObject()readObject()是 HashSet 自己不得不实现之外,其他方法都是直接调用 HashMap 中的方法。

HashMap HashSet
实现了 Map 接口 实现 Set 接口
存储键值对 仅存储对象
调用 put()向 map 中添加元素 调用 add()方法向 Set 中添加元素
HashMap 使用键(Key)计算 Hashcode HashSet 使用成员对象来计算 hashcode 值,对于两个对象来说 hashcode 可能相同,所以 equals() 方法用来判断对象的相等性,

HashSet 如何检查重复

当你把对象加入HashSet时,HashSet 会先计算对象的hashcode值来判断对象加入的位置,同时也会与其他加入的对象的 hashcode 值作比较,如果没有相符的 hashcode,HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象,这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同,HashSet 就不会让加入操作成功。(摘自我的 Java 启蒙书《Head fist java》第二版)

hashCode()与 equals()的相关规定:

  1. 如果两个对象相等,则 hashcode 一定也是相同的
  2. 两个对象相等, 对两个 equals 方法返回 true
  3. 两个对象有相同的 hashcode 值,它们也不一定是相等的(两个哈希码相同的对象,可能是同一个对象,也可能是不同的对象(比如字符串))
  4. 综上,equals 方法被覆盖过,则 hashCode 方法也必须被覆盖(字符串例子)
  5. hashCode() 的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode(),则该 class 的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)

HashMap 的底层实现

JDK1.8 之前

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值,然后通过 (n - 1) & hash 判断当前元素存放的位置(这里的 n 指的是数组的长度),如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash 值以及 key 是否相同,如果相同的话,直接覆盖,不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。(hash()扰动函数减少碰撞)

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化,但是原理不变。

1
2
3
4
5
  static final int hash(Object key) { //jdk1.8
int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //移位运算,扰动函数
}

对比一下 JDK1.7 的 HashMap 的 hash 方法源码.

1
2
3
4
5
6
7
8
static int hash(int h) { //jdk1.7




h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法 ,JDK 1.7 的 hash 方法的性能会稍差一点点,因为毕竟扰动了 4 次。

所谓 “拉链法” 就是:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。

img

JDK1.8 之后

相比于之前的版本, JDK1.8 之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)时,将链表转化为红黑树,以减少搜索时间。

img

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。

HashMap 的长度为什么是 2 的幂次方

为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀。我们上面也讲到了过了,Hash 值的范围值 - 2147483648 到 2147483647,前后加起来大概 40 亿的映射空间,只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组,内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是 “ (n - 1) & hash”。(n 代表数组长度)。这也就解释了 HashMap 的长度为什么是 2 的幂次方。(将哈希值mod n就可以算出key的索引,但是由于位运算比mod运算更快,所以通过位运算&来计算,这里存在一个数学关系—-当length为2的n次方时,h & (table.length -1)==(h%length))

这个算法应该如何设计呢?

我们首先可能会想到采用 % 取余的操作来实现。但是,重点来了:“取余 (%) 操作中如果除数是 2 的幂次则等价于与其除数减一的与 (&) 操作(也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方;)。” 并且 采用二进制位操作 &,相对于 % 能够提高运算效率,这就解释了 HashMap 的长度为什么是 2 的幂次方。

HashMap 多线程操作导致死循环问题

主要原因在于 并发下的 Rehash 会造成元素之间会形成一个循环链表。不过,jdk 1.8 后解决了这个问题,但是还是不建议在多线程下使用 HashMap, 因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。(JDK1.8以前,在并发环境下,两个线程操作同一个map时,在put的时候,若存放的元素大于阈值(Capacity * loadFactor负载因子),会进行扩容Rehash;在此之前,所有的元素已经put进旧的map;扩容的时候,两个线程会分别形成一个新的map)。下次取put(11)时会形成死循环

img

详情请查看:

疫苗:JAVA HASHMAP的死循环

拓展:

  • 同时put造成的数据丢失

  • 扩容机制造成的数据丢失问题

    • 当当前map到达阈值的同时,多个线程同时进行put操作,此时均会去重新去创建数组并获取hash值进行原map中数据的复制。此时只有最后一个线程生成的table可以保留,其他的均会丢失。
    • 当某些线程已经扩容完毕,但有的(A)线程刚开始进行扩容,会造成(A)线程会将已经扩容的map当做原需要扩容的map,在已经扩容完毕的基础上再次进行扩容操作,

Java 8系列之重新认识HashMap

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

  • 底层数据结构: JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组 + 链表 实现,JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样,数组 + 链表 / 红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组 + 链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的;

  • 实现线程安全的方式(重要):在 JDK1.7 的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段 (Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念,而是直接用 Node 数组 + 链表 + 红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6 以后 对 synchronized 锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在 JDK1.8 中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;② Hashtable(同一把锁) : 使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。

  • 总结:

    • JDK1.8之前,ConcurrentHashMap底层数据结构(分段数组+链表),同步机制采用分段锁;JDK1.8后,采用数组+链表/红黑树,同步机制摒弃分段锁,采用synchronizedCAS
    • JDK1.7时,HashTable底层数据结构(数组+链表)

    两者的对比图:

    图片来源:http://www.cnblogs.com/chengxiao/p/6842045.html

    HashTable:

    img

JDK1.7 的 ConcurrentHashMap:

img

JDK1.8 的 ConcurrentHashMap(TreeBin: 红黑二叉树节点 Node: 链表节点):

img

ConcurrentHashMap 线程安全的具体实现方式 / 底层具体实现

JDK1.7(上面有示意图)

首先将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成

Segment 实现了 ReentrantLock([rɪ’entrənt]), 所以 Segment 是一种可重入锁,扮演锁的角色。HashEntry 用于存储键值对数据。

1
2
static class Segment<K,V> extends ReentrantLock implements Serializable {
}

一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap 类似,是一种数组和链表结构,一个 Segment 包含一个 HashEntry 数组,每个 HashEntry 是一个链表结构的元素,每个 Segment 守护着一个 HashEntry 数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 的锁。

总结:

  • 一个ConcurrentHashMap包含了一个Segment数组
  • 一个Segment元素里包含了一个HashEntry数组
  • 一个HashEntry元素包含了链表结构

JDK1.8 (上面有示意图)

ConcurrentHashMap 取消了 Segment 分段锁,采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似,数组 + 链表 / 红黑二叉树。Java 8 在链表长度超过一定阈值(8)时将链表(寻址时间复杂度为 O(N))转换为红黑树(寻址时间复杂度为 O(log(N)))

synchronized 只锁定当前链表或红黑二叉树的首节点,这样只要 hash 不冲突,就不会产生并发,效率又提升 N 倍。

comparable 和 Comparator 的区别

  • comparable 接口实际上是出自 java.lang 包 它有一个 compareTo(Object obj)方法用来排序
  • comparator 接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用来排序

一般我们需要对一个集合使用自定义排序时,我们就要重写compareTo()方法或compare()方法,当我们需要对某一个集合实现两种排序方式,比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话,我们可以重写compareTo()方法和使用自制的 Comparator 方法或者以两个 Comparator 来实现歌名排序和歌星名排序,第二种代表我们只能使用两个参数版的 Collections.sort().

Comparator 定制排序

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
ArrayList<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(-1);
arrayList.add(3);
arrayList.add(3);
arrayList.add(-5);
arrayList.add(7);
arrayList.add(4);
arrayList.add(-9);
arrayList.add(-7);
System.out.println("原始数组:");
System.out.println(arrayList);

Collections.reverse(arrayList);
System.out.println("Collections.reverse(arrayList):");
System.out.println(arrayList);


Collections.sort(arrayList);
System.out.println("Collections.sort(arrayList):");
System.out.println(arrayList);

Collections.sort(arrayList, new Comparator<Integer>() { //匿名内部类

@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
System.out.println("定制排序后:");
System.out.println(arrayList);

Output:

1
2
3
4
5
6
7
8
原始数组:
[-1, 3, 3, -5, 7, 4, -9, -7]
Collections.reverse(arrayList):
[-7, -9, 4, 7, -5, 3, 3, -1]
Collections.sort(arrayList):
[-9, -7, -5, -1, 3, 3, 4, 7]
定制排序后:
[7, 4, 3, 3, -1, -5, -7, -9]

重写 compareTo 方法实现按年龄来排序

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
public  class Person implements Comparable<Person> {
private String name;
private int age;

public Person(String name, int age) {
super();
this.name = name;
this.age = age;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public int getAge() {
return age;
}

public void setAge(int age) {
this.age = age;
}


@Override
public int compareTo(Person o) { //重写

if (this.age > o.getAge()) {
return 1;
} else if (this.age < o.getAge()) {
return -1;
}
return age;
}
}
public static void main(String[] args) {
TreeMap<Person, String> pdata = new TreeMap<Person, String>(); //TreeMap,可以对插入的Key按照重写的排序规则进行排序
pdata.put(new Person("张三", 30), "zhangsan");
pdata.put(new Person("李四", 20), "lisi");
pdata.put(new Person("王五", 10), "wangwu");
pdata.put(new Person("小红", 5), "xiaohong");

Set<Person> keys = pdata.keySet();
for (Person key : keys) {
System.out.println(key.getAge() + "-" + key.getName());

}
}

Output:

1
2
3
4
5-小红
10-王五
20-李四
30-张三

总结:

  • 均为接口

  • Comparable—-compareTo(obj)—-实现重写

  • Compartor—-compare(obj1,obj2) —-匿名内部类

    • Collections.sort(List<T> list, Comparator<? super T> c) //集合中使用比较器

集合框架底层数据结构总结

Collection

1. List

  • Arraylist: Object 数组
  • Vector: Object 数组
  • LinkedList: 双向链表 (JDK1.6 之前为循环链表,JDK1.7 取消了循环)

2. Set

  • HashSet(无序,唯一): 基于 HashMap 实现的,底层采用 HashMap 来保存元素(此处无序指的是,排列顺序不取决于存放顺序,而是按照hash值排列)
  • LinkedHashSet: LinkedHashSet 继承于 HashSet,并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现一样,不过还是有一点点区别的
  • TreeSet(有序,唯一): 红黑树 (自平衡的排序二叉树)(此处的有序指的是存入的元素按照指定的排序规则排序)

Map

  • HashMap: JDK1.8 之前 HashMap 由数组 + 链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法” 解决冲突)。JDK1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)时,将链表转化为红黑树,以减少搜索时间
  • LinkedHashMap: LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外,LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。详细可以查看:《LinkedHashMap 源码详细分析(JDK1.8)》
  • Hashtable: 数组 + 链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的
  • TreeMap: 红黑树(自平衡的排序二叉树)

如何选用集合?

主要根据集合的特点来选用,比如我们需要根据键值获取到元素值时就选用 Map 接口下的集合,需要排序时选择 TreeMap, 不需要排序时就选择 HashMap, 需要保证线程安全就选用 ConcurrentHashMap. 当我们只需要存放元素值时,就选择实现 Collection 接口的集合,需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet,不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList,然后再根据实现这些接口的集合的特点来选用。

问题:

hashmap底层红黑树? 碰撞超过阈值8

了解红黑树增删

来了解hashmap的扩容机制和hash算法

hashset是怎么实现的? hashmap是怎么实现hashset的?

扰动函数?

ReentrantLock,可重入锁

1.8ConcurrentHashMap利用CAS和Synchronized锁?

JDK1.8接口可以自己实现某个方法,作用是什么?

总结:

堆内存:对象

栈内存:引用

如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap

任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。

TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。

HashMap底层数据结构是链表数组(哈希桶数组),通过拉链法解决哈希碰撞,为了减少哈希碰撞发生,需要一个好的扩容机制和hash算法;在jdk1.7和jdk1.8的时候,由于两种哈希算法与扩容机制都做得不错,所以hash分布均匀,不容易发生碰撞;在极端情况下,若有多数相同的对象,则会产生相同的hash值,在大量的碰撞下,jdk1.7的get方法时间直线上升,jdk1.8在检测到碰撞增多后,将链表更改成了红黑树;红黑树本质是一颗二叉查找树,但是由于其红黑节点的特性,在删除与新增节点时,需要保持树的特点,从而保证n个元素的高度永远近似lgn;相较于二叉查找树,有可能退化成线性链表,从而使树的高度变为n,从而降低查找效率;

接口可以继承多个接口,抽象类可以实现部分接口,普通类需要实现全部接口;抽象类继承接口,可以减少普通类对于接口全部方法的重写,减少代码冗余

匿名内部类:在类里直接定义接口、抽象类、普通类的方法,作用是解决某些接口的方法在一些类里只执行一次,若重写一个类来实现接口里的方法,过于冗余

多态:

  • 向上转型:父类引用指向子类对象

    • 作用:若不同的类需要对同一种方法进行不同的重写,那么就利用向上转型;这样父类里的方法就会被重写,从而解决了引用对象时需要重载多个方法;使代码易于拓展
    • 例子:跳舞,有男人跳舞和女人跳舞,若在一个方法里引入男人和女人跳舞,那么需要写两个方法;但是如果利用向上转型,传入父类,那么只用实现一个方法
  • 向下转型:父类引用指向子类对象,父类引用强转成子类

    • 作用:将同一类型的多个类可以被存放在同一个集合里
    • 例子:比如需要使用集合存放电子产品,不使用接口是做不到存放到同一个集合里的,需要使用多个不同的集合才可以存放;当取出集合里的元素时,需要使用向下转型,才可以调用属于子类的专有方法

    向上转型

    向下转型

@Override重写标志,若在子类中重写方法,不加这个标志也起作用;加这个标志,起检查作用,若重写的方法父类中没有,在预编译时会出错;建议在代码中加,否则重写的方法名出错的话,未检查的话很难排查出来

0%