0%

使用Map

我们知道,List是一种顺序列表,如果有一个存储学生Student实例的List,要在List中根据name查找某个指定的Student的分数,应该怎么办?

最简单的方法是遍历List并判断name是否相等,然后返回指定元素:

1
2
3
4
5
6
7
8
9
List<Student> list = ...
Student target = null;
for (Student s : list) {
if ("Xiao Ming".equals(s.name)) {
target = s;
break;
}
}
System.out.println(target.score);

这种需求其实非常常见,即通过一个键去查询对应的值。使用List来实现存在效率非常低的问题,因为平均需要扫描一半的元素才能确定,而Map这种键值(key-value)映射表的数据结构,作用就是能高效通过key快速查找value(元素)。

Map是一种键-值映射表,当我们调用put(K key, V value)方法时,就把keyvalue做了映射并放入Map。当我们调用V get(K key)时,就可以通过key获取到对应的value。如果key不存在,则返回null。和List类似,Map也是一个接口,最常用的实现类是HashMap

如果只是想查询某个key是否存在,可以调用boolean containsKey(K key)方法。

如果我们在存储Map映射关系的时候,对同一个key调用两次put()方法,分别放入不同的value,会有什么问题呢?

重复放入key-value并不会有任何问题,但是一个key只能关联一个valueput()方法的签名是V put(K key, V value),如果放入的key已经存在,put()方法会返回被删除的旧的value,否则,返回null

始终牢记:Map中不存在重复的key,因为放入相同的key,只会把原有的key-value对应的value给替换掉。

此外,在一个Map中,虽然key不能重复,但value是可以重复的:

1
2
3
Map<String, Integer> map = new HashMap<>();
map.put("apple", 123);
map.put("pear", 123); // ok

遍历Map

Map来说,要遍历key可以使用for each循环遍历Map实例的keySet()方法返回的Set集合,它包含不重复的key的集合:

1
2
3
4
5
6
7
8
9
10
11
12
public class Main {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("apple", 123);
map.put("pear", 456);
map.put("banana", 789);
for (String key : map.keySet()) {
Integer value = map.get(key);
System.out.println(key + " = " + value);
}
}
}

同时遍历keyvalue可以使用for each循环遍历Map对象的entrySet()集合,它包含每一个key-value映射:

1
2
3
4
5
6
7
8
9
10
11
12
public class Main {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("apple", 123);
map.put("pear", 456);
map.put("banana", 789);
for (Map.Entry<String, Integer> entry : map.entrySet()) {
String key = entry.getKey();
Integer value = entry.getValue();
System.out.println(key + " = " + value);
}
}

Map存储的是key-value的映射关系,并且,它不保证顺序。在遍历的时候,遍历的顺序既不一定是put()时放入的key的顺序,也不一定是key的排序顺序。使用Map时,任何依赖顺序的逻辑都是不可靠的。以HashMap为例,假设我们放入"A""B""C"这3个key遍历的时候,每个key会保证被遍历一次且仅遍历一次,但顺序完全没有保证,甚至对于不同的JDK版本,相同的代码遍历的输出顺序都是不同的!

小结

Map是一种映射表,可以通过key快速查找value

可以通过for each遍历keySet(),也可以通过for each遍历entrySet(),直接获取key-value

最常用的一种Map实现是HashMap

编写equals和hashCode

我们知道Map是一种键-值(key-value)映射表,可以通过key快速查找对应的value。

以HashMap为例,观察下面的代码:

1
2
3
4
5
6
7
Map<String, Person> map = new HashMap<>();
map.put("a", new Person("Xiao Ming"));
map.put("b", new Person("Xiao Hong"));
map.put("c", new Person("Xiao Jun"));

map.get("a"); // Person("Xiao Ming")
map.get("x"); // null

HashMap之所以能根据key直接拿到value,原因是它内部通过空间换时间的方法,用一个大数组存储所有value,并根据key直接计算出value应该存储在哪个索引:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  ┌───┐
0 │ │
├───┤
1 │ ●─┼───> Person("Xiao Ming")
├───┤
2 │ │
├───┤
3 │ │
├───┤
4 │ │
├───┤
5 │ ●─┼───> Person("Xiao Hong")
├───┤
6 │ ●─┼───> Person("Xiao Jun")
├───┤
7 │ │
└───┘

如果key的值为"a",计算得到的索引总是1,因此返回valuePerson("Xiao Ming"),如果key的值为"b",计算得到的索引总是5,因此返回valuePerson("Xiao Hong"),这样,就不必遍历整个数组,即可直接读取key对应的value

当我们使用key存取value的时候,就会引出一个问题:

我们放入Mapkey是字符串"a",但是,当我们获取Mapvalue时,传入的变量不一定就是放入的那个key对象。

换句话讲,两个key应该是内容相同,但不一定是同一个对象。测试代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Main {
public static void main(String[] args) {
String key1 = "a";
Map<String, Integer> map = new HashMap<>();
map.put(key1, 123);

String key2 = new String("a");
map.get(key2); // 123

System.out.println(key1 == key2); // false
System.out.println(key1.equals(key2)); // true
}
}

因为在Map的内部,对key做比较是通过equals()实现的,这一点和List查找元素需要正确覆写equals()是一样的,即正确使用Map必须保证:作为key的对象必须正确覆写equals()方法。

我们经常使用String作为key,因为String已经正确覆写了equals()方法。但如果我们放入的key是一个自己写的类,就必须保证正确覆写了equals()方法。

我们再思考一下HashMap为什么能通过key直接计算出value存储的索引。相同的key对象(使用equals()判断时返回true)必须要计算出相同的索引,否则,相同的key每次取出的value就不一定对。

通过key计算索引的方式就是调用key对象的hashCode()方法,它返回一个int整数。HashMap正是通过这个方法直接定位key对应的value的索引,继而直接返回value

因此,正确使用Map必须保证:

  1. 作为key的对象必须正确覆写equals()方法,相等的两个key实例调用equals()必须返回true
  2. 作为key的对象还必须正确覆写hashCode()方法,且hashCode()方法要严格遵循以下规范:
  • 如果两个对象相等,则两个对象的hashCode()必须相等;
  • 如果两个对象不相等,则两个对象的hashCode()尽量不要相等。(减少hash碰撞)

即对应两个实例ab

  • 如果ab相等,那么a.equals(b)一定为true,则a.hashCode()必须等于b.hashCode()
  • 如果ab不相等,那么a.equals(b)一定为false,则a.hashCode()b.hashCode()尽量不要相等。

上述第一条规范是正确性,必须保证实现,否则HashMap不能正常工作。

而第二条如果尽量满足,则可以保证查询效率,因为不同的对象,如果返回相同的hashCode(),会造成Map内部存储冲突,使存取的效率下降。

正确编写equals()的方法我们已经在编写equals方法一节中讲过了,以Person类为例:

1
2
3
4
5
public class Person {
String firstName;
String lastName;
int age;
}

把需要比较的字段找出来:

  • firstName
  • lastName
  • age

然后,引用类型使用Objects.equals()比较,基本类型使用==比较。

在正确实现equals()的基础上,我们还需要正确实现hashCode(),即上述3个字段分别相同的实例,hashCode()返回的int必须相同:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Person {
String firstName;
String lastName;
int age;

@Override
int hashCode() {
int h = 0;
h = 31 * h + firstName.hashCode();
h = 31 * h + lastName.hashCode();
h = 31 * h + age;
return h;
}
}

注意到String类已经正确实现了hashCode()方法,我们在计算PersonhashCode()时,反复使用31*h,这样做的目的是为了尽量把不同的Person实例的hashCode()均匀分布到整个int范围。

和实现equals()方法遇到的问题类似,如果firstNamelastNamenull上述代码工作起来就会抛NullPointerException。为了解决这个问题,我们在计算hashCode()的时候,经常借助Objects.hash()来计算

1
2
3
int hashCode() {
return Objects.hash(firstName, lastName, age);
}

所以,编写equals()hashCode()遵循的原则是:

equals()用到的用于比较的每一个字段,都必须在hashCode()中用于计算;equals()中没有使用到的字段,绝不可放在hashCode()中计算。

另外注意,对于放入HashMapvalue对象,没有任何要求。

延伸阅读

既然HashMap内部使用了数组,通过计算keyhashCode()直接定位value所在的索引,那么第一个问题来了:hashCode()返回的int范围高达±21亿,先不考虑负数,HashMap内部使用的数组得有多大?

实际上HashMap初始化时默认的数组大小只有16,任何key,无论它的hashCode()有多大,都可以简单地通过:

1
int index = key.hashCode() & 0xf; // 0xf = 15

把索引确定在0~15,即永远不会超出数组范围,上述算法只是一种最简单的实现。

第二个问题:如果添加超过16个key-valueHashMap,数组不够用了怎么办?

添加超过一定数量的key-value时,HashMap会在内部自动扩容,每次扩容一倍,即长度为16的数组扩展为长度32,相应地,需要重新确定hashCode()计算的索引位置。例如,对长度为32的数组计算hashCode()对应的索引,计算方式要改为:

1
int index = key.hashCode() & 0x1f; // 0x1f = 31

由于扩容会导致重新分布已有的key-value,所以,频繁扩容对HashMap的性能影响很大。如果我们确定要使用一个容量为10000key-valueHashMap,更好的方式是创建HashMap时就指定容量:

1
Map<String, Integer> map = new HashMap<>(10000);

虽然指定容量是10000,但HashMap内部的数组长度总是2n,因此,实际数组长度被初始化为比10000大的16384(214)。

HashMap内部,可能存在不同的key,映射到相同的hashCode(),即相同的数组索引上,肿么办?

我们就假设"a""b"这两个key最终计算出的索引都是5,那么,在HashMap的数组中,实际存储的不是一个Person实例,而是一个List,它包含两个Entry,一个是"a"的映射,一个是"b"的映射:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  ┌───┐
0 │ │
├───┤
1 │ │
├───┤
2 │ │
├───┤
3 │ │
├───┤
4 │ │
├───┤
5 │ ●─┼───> List<Entry<String, Person>>
├───┤
6 │ │
├───┤
7 │ │
└───┘

在查找的时候,例如:

1
Person p = map.get("a");

HashMap内部通过"a"找到的实际上是List>,它还需要遍历这个List,并找到一个Entry,它的key字段是"a",才能返回对应的Person实例。

我们把不同的key具有相同的hashCode()的情况称之为哈希冲突。在冲突的时候,一种最简单的解决办法是用List存储hashCode()相同的key-value。显然,如果冲突的概率越大,这个List就越长,Mapget()方法效率就越低,这就是为什么要尽量满足条件二:

如果两个对象不相等,则两个对象的hashCode()尽量不要相等。

hashCode()方法编写得越好,HashMap工作的效率就越高。

小结

要正确使用HashMap,作为key的类必须正确覆写equals()hashCode()方法;

一个类如果覆写了equals(),就必须覆写hashCode(),并且覆写规则是:

  • 如果equals()返回true,则hashCode()返回值必须相等;
  • 如果equals()返回false,则hashCode()返回值尽量不要相等。

实现hashCode()方法可以通过Objects.hashCode()辅助方法实现。

使用EnumMap

因为HashMap是一种通过对key计算hashCode(),通过空间换时间的方式,直接定位到value所在的内部数组的索引,因此,查找效率非常高。

如果作为key的对象是enum类型,那么,还可以使用Java集合库提供的一种EnumMap,它在内部以一个非常紧凑的数组存储value,并且根据enum类型的key直接定位到内部数组的索引,并不需要计算hashCode(),不但效率最高,而且没有额外的空间浪费。

我们以DayOfWeek这个枚举类型为例,为它做一个“翻译”功能:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Main {
public static void main(String[] args) {
Map<DayOfWeek, String> map = new EnumMap<>(DayOfWeek.class);
map.put(DayOfWeek.MONDAY, "星期一");
map.put(DayOfWeek.TUESDAY, "星期二");
map.put(DayOfWeek.WEDNESDAY, "星期三");
map.put(DayOfWeek.THURSDAY, "星期四");
map.put(DayOfWeek.FRIDAY, "星期五");
map.put(DayOfWeek.SATURDAY, "星期六");
map.put(DayOfWeek.SUNDAY, "星期日");
System.out.println(map);
System.out.println(map.get(DayOfWeek.MONDAY));
}
}

使用EnumMap的时候,我们总是用Map接口来引用它,因此,实际上把HashMapEnumMap互换,在客户端看来没有任何区别。

小结

如果Map的key是enum类型,推荐使用EnumMap,既保证速度,也不浪费空间。

使用EnumMap的时候,根据面向抽象编程的原则,应持有Map接口。

使用TreeMap

我们已经知道,HashMap是一种以空间换时间的映射表,它的实现原理决定了内部的Key是无序的,即遍历HashMap的Key时,其顺序是不可预测的(但每个Key都会遍历一次且仅遍历一次)。

还有一种Map,它在内部会对Key进行排序,这种Map就是SortedMap。注意到SortedMap是接口,它的实现类是TreeMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
       ┌───┐
│Map│
└───┘

┌────┴─────┐
│ │
┌───────┐ ┌─────────┐
│HashMap│ │SortedMap│
└───────┘ └─────────┘


┌─────────┐
│ TreeMap │
└─────────┘

SortedMap保证遍历时以Key的顺序来进行排序。例如,放入的Key是"apple""pear""orange",遍历的顺序一定是"apple""orange""pear",因为String默认按字母排序.

使用TreeMap时,放入的Key必须实现Comparable接口。StringInteger这些类已经实现了Comparable接口,因此可以直接作为Key使用。作为Value的对象则没有任何要求。

如果作为Key的class没有实现Comparable接口,那么,必须在创建TreeMap时同时指定一个自定义排序算法:

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
public class Main {
public static void main(String[] args) {
Map<Person, Integer> map = new TreeMap<>(new Comparator<Person>() {
public int compare(Person p1, Person p2) {
return p1.name.compareTo(p2.name);
}
});
map.put(new Person("Tom"), 1);
map.put(new Person("Bob"), 2);
map.put(new Person("Lily"), 3);
for (Person key : map.keySet()) {
System.out.println(key);
}
// {Person: Bob}, {Person: Lily}, {Person: Tom}
System.out.println(map.get(new Person("Bob"))); // 2
}
}

class Person {
public String name;
Person(String name) {
this.name = name;
}
public String toString() {
return "{Person: " + name + "}";
}
}

注意到Comparator接口要求实现一个比较方法,它负责比较传入的两个元素ab,如果a<b,则返回负数,通常是-1,如果a==b,则返回0,如果a>b,则返回正数,通常是1TreeMap内部根据比较结果对Key进行排序。

从上述代码执行结果可知,打印的Key确实是按照Comparator定义的顺序排序的。如果要根据Key查找Value,我们可以传入一个new Person("Bob")作为Key,它会返回对应的Integer2

另外,注意到Person类并未覆写equals()hashCode()因为TreeMap不使用equals()hashCode()

我们来看一个稍微复杂的例子:这次我们定义了Student类,并用分数score进行排序,高分在前:

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
public class Main {
public static void main(String[] args) {
Map<Student, Integer> map = new TreeMap<>(new Comparator<Student>() {
public int compare(Student p1, Student p2) {
return p1.score > p2.score ? -1 : 1;
}
});
map.put(new Student("Tom", 77), 1);
map.put(new Student("Bob", 66), 2);
map.put(new Student("Lily", 99), 3);
for (Student key : map.keySet()) {
System.out.println(key);
}
System.out.println(map.get(new Student("Bob", 66))); // null?
}
}

class Student {
public String name;
public int score;
Student(String name, int score) {
this.name = name;
this.score = score;
}
public String toString() {
return String.format("{%s: score=%d}", name, score);
}
}

for循环中,我们确实得到了正确的顺序。但是,且慢!根据相同的Key:new Student("Bob", 66)进行查找时,结果为null

这是怎么肥四?难道TreeMap有问题?遇到TreeMap工作不正常时,我们首先回顾Java编程基本规则:出现问题,不要怀疑Java标准库,要从自身代码找原因。

在这个例子中,TreeMap出现问题,原因其实出在这个Comparator上:

1
2
3
public int compare(Student p1, Student p2) {
return p1.score > p2.score ? -1 : 1;
}

p1.scorep2.score不相等的时候,它的返回值是正确的,但是,在p1.scorep2.score相等的时候,它并没有返回0这就是为什么TreeMap工作不正常的原因:TreeMap在比较两个Key是否相等时,依赖Key的compareTo()方法或者Comparator.compare()方法。在两个Key相等时,必须返回0。因此,修改代码如下:

1
2
3
4
5
6
public int compare(Student p1, Student p2) {
if (p1.score == p2.score) {
return 0;
}
return p1.score > p2.score ? -1 : 1;
}

或者直接借助Integer.compare(int, int)也可以返回正确的比较结果。

小结

SortedMap在遍历时严格按照Key的顺序遍历,最常用的实现类是TreeMap

作为SortedMap的Key必须实现Comparable接口,或者传入Comparator

要严格按照compare()规范实现比较逻辑,否则,TreeMap将不能正常工作。


本文整理自

使用Map

编写equals和hashCode

使用EnumMap

使用TreeMap

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!


使用List

在集合类中,List是最基础的一种集合:它是一种有序列表。

List的行为和数组几乎完全相同:List内部按照放入元素的先后顺序存放,每个元素都可以通过索引确定自己的位置,List的索引和数组一样,从0开始。

数组和List类似,也是有序结构,如果我们使用数组,在添加和删除元素的时候,会非常不方便。例如,从一个已有的数组{'A', 'B', 'C', 'D', 'E'}中删除索引为2的元素:

1
2
3
4
5
6
7
8
9
10
11
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │ │
└───┴───┴───┴───┴───┴───┘
│ │
┌───┘ │
│ ┌───┘
│ │
▼ ▼
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ D │ E │ │ │
└───┴───┴───┴───┴───┴───┘

这个“删除”操作实际上是把'C'后面的元素依次往前挪一个位置,而“添加”操作实际上是把指定位置以后的元素都依次向后挪一个位置,腾出来的位置给新加的元素。这两种操作,用数组实现非常麻烦。

因此,在实际应用中,需要增删元素的有序列表,我们使用最多的是ArrayList。实际上,ArrayList在内部使用了数组来存储所有元素。例如,一个ArrayList拥有5个元素,实际数组大小为6(即有一个空位):

1
2
3
4
size=5
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │ │
└───┴───┴───┴───┴───┴───┘

当添加一个元素并指定索引到ArrayList时,ArrayList自动移动需要移动的元素:

1
2
3
4
size=5
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ │ C │ D │ E │
└───┴───┴───┴───┴───┴───┘

然后,往内部指定索引的数组位置添加一个元素,然后把size1

1
2
3
4
size=6
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ F │ C │ D │ E │
└───┴───┴───┴───┴───┴───┘

继续添加元素,但是数组已满,没有空闲位置的时候,ArrayList先创建一个更大的新数组,然后把旧数组的所有元素复制到新数组,紧接着用新数组取代旧数组:

1
2
3
4
size=6
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ F │ C │ D │ E │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

现在,新数组就有了空位,可以继续添加一个元素到数组末尾,同时size1

1
2
3
4
size=7
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ F │ C │ D │ E │ G │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

可见,ArrayList把添加和删除的操作封装起来,让我们操作List类似于操作数组,却不用关心内部元素如何移动。

我们考察List接口,可以看到几个主要的接口方法:

  • 在末尾添加一个元素:void add(E e)
  • 在指定索引添加一个元素:void add(int index, E e)
  • 删除指定索引的元素:int remove(int index)
  • 删除某个元素:int remove(Object e)
  • 获取指定索引的元素:E get(int index)
  • 获取链表大小(包含元素的个数):int size()

但是,实现List接口并非只能通过数组(即ArrayList的实现方式)来实现,另一种LinkedList通过“链表”也实现了List接口。在LinkedList中,它的内部每个元素都指向下一个元素:

1
2
3
        ┌───┬───┐   ┌───┬───┐   ┌───┬───┐   ┌───┬───┐
HEAD ──>│ A │ ●─┼──>│ B │ ●─┼──>│ C │ ●─┼──>│ D │ │
└───┴───┘ └───┴───┘ └───┴───┘ └───┴───┘

我们来比较一下ArrayListLinkedList

ArrayList LinkedList
获取指定元素 速度很快 需要从头开始查找元素
添加元素到末尾 速度很快 速度很快
在指定位置添加/删除 需要移动元素 不需要移动元素
内存占用 较大

通常情况下,我们总是优先使用ArrayList

List的特点

使用List时,我们要关注List接口的规范。List接口允许我们添加重复的元素,即List内部的元素可以重复,List还允许添加null.

创建List

除了使用ArrayListLinkedList,自JDK 9以后, 我们还可以通过List接口提供的of()方法,根据给定元素快速创建List

1
List<Integer> list = List.of(1, 2, 5);

但是List.of()方法不接受null值,如果传入null,会抛出NullPointerException异常。

遍历List

和数组类型,我们要遍历一个List,完全可以用for循环根据索引配合get(int)方法遍历:

1
2
3
4
5
6
7
8
9
public class Main {
public static void main(String[] args) {
List<String> list = List.of("apple", "pear", "banana");
for (int i=0; i<list.size(); i++) {
String s = list.get(i);
System.out.println(s);
}
}
}

但这种方式并不推荐,一是代码复杂,二是因为get(int)方法只有ArrayList的实现是高效的,换成LinkedList后,索引越大,访问速度越慢。

所以我们要始终坚持使用迭代器Iterator来访问ListIterator本身也是一个对象,但它是由List的实例调用iterator()方法的时候创建的。Iterator对象知道如何遍历一个List,并且不同的List类型,返回的Iterator对象实现也是不同的,但总是具有最高的访问效率。

Iterator对象有两个方法:boolean hasNext()判断是否有下一个元素,E next()返回下一个元素。因此,使用Iterator遍历List代码如下:

1
2
3
4
5
6
7
8
9
public class Main {
public static void main(String[] args) {
List<String> list = List.of("apple", "pear", "banana");
for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
String s = it.next();
System.out.println(s);
}
}
}

有童鞋可能觉得使用Iterator访问List的代码比使用索引更复杂。但是,要记住,通过Iterator遍历List永远是最高效的方式。并且,由于Iterator遍历是如此常用,所以,Java的for each循环本身就可以帮我们使用Iterator遍历。把上面的代码再改写如下:

1
2
3
4
5
6
7
8
public class Main {
public static void main(String[] args) {
List<String> list = List.of("apple", "pear", "banana");
for (String s : list) {
System.out.println(s);
}
}
}

上述代码就是我们编写遍历List的常见代码。

实际上,只要实现了Iterable接口的集合类都可以直接用for each循环来遍历,Java编译器本身并不知道如何遍历集合对象,但它会自动把for each循环变成Iterator的调用,原因就在于Iterable接口定义了一个Iterator iterator()方法,强迫集合类必须返回一个Iterator实例。

List和Array转换

List变为Array有三种方法,第一种是调用toArray()方法直接返回一个Object[]数组:

1
2
3
4
5
6
7
8
9
public class Main {
public static void main(String[] args) {
List<String> list = List.of("apple", "pear", "banana");
Object[] array = list.toArray();
for (Object s : array) {
System.out.println(s);
}
}
}

这种方法会丢失类型信息(降为Object),所以实际应用很少。

第二种方式是给toArray(T[])传入一个类型相同的ArrayList内部自动把元素复制到传入的Array中:

1
2
3
4
5
6
7
8
9
public class Main {
public static void main(String[] args) {
List<Integer> list = List.of(12, 34, 56);
Integer[] array = list.toArray(new Integer[3]);
for (Integer n : array) {
System.out.println(n);
}
}
}

注意到这个toArray(T[])方法的泛型参数并不是`List`接口定义的泛型参数,所以,我们实际上可以传入其他类型的数组,例如我们传入Number类型的数组,返回的仍然是Number类型:

1
2
3
4
5
6
7
8
9
public class Main {
public static void main(String[] args) {
List<Integer> list = List.of(12, 34, 56);
Number[] array = list.toArray(new Number[3]);
for (Number n : array) {
System.out.println(n);
}
}
}

但是,如果我们传入类型不匹配的数组,例如,String[]类型的数组,由于List的元素是Integer,所以无法放入String数组,这个方法会抛出ArrayStoreException

如果我们传入的数组大小和List实际的元素个数不一致怎么办?根据List接口的文档,我们可以知道:

如果传入的数组不够大,那么List内部会创建一个新的刚好够大的数组,填充后返回;如果传入的数组比List元素还要多,那么填充完元素后,剩下的数组元素一律填充null

实际上,最常用的是传入一个“恰好”大小的数组:

1
Integer[] array = list.toArray(new Integer[list.size()]);

最后一种更简洁的写法是通过List接口定义的T[] toArray(IntFunction generator)方法:

1
Integer[] array = list.toArray(Integer[]::new);

这种函数式写法我们会在后续讲到。

反过来,把Array变为List就简单多了,JDK 11可以通过List.of(T...)方法最简单:

1
2
Integer[] array = { 1, 2, 3 };
List<Integer> list = List.of(array);

对于JDK 11之前的版本,可以使用Arrays.asList(T...)方法把数组转换成List

要注意的是,返回的List不一定就是ArrayList或者LinkedList,因为List只是一个接口,如果我们调用List.of(),它返回的是一个只读List

1
2
3
4
5
6
public class Main {
public static void main(String[] args) {
List<Integer> list = List.of(12, 34, 56);
list.add(999); // UnsupportedOperationException
}
}

对只读List调用add()remove()方法会抛出UnsupportedOperationException

小结

List是按索引顺序访问的长度可变的有序表,优先使用ArrayList而不是LinkedList

可以直接使用for each遍历List

List可以和Array相互转换。

编写equals方法

我们知道List是一种有序链表:List内部按照放入元素的先后顺序存放,并且每个元素都可以通过索引确定自己的位置。

List还提供了boolean contains(Object o)方法来判断List是否包含某个指定元素。此外,int indexOf(Object o)方法可以返回某个元素的索引,如果元素不存在,就返回-1

我们来看一个例子:

import java.util.List; Run

这里我们注意一个问题,我们往List中添加的"C"和调用contains("C")传入的"C"是不是同一个实例?

如果这两个"C"不是同一个实例,这段代码是否还能得到正确的结果?我们可以改写一下代码测试一下:

1
import java.util.List;

Run

true
2

因为我们传入的是new String("C"),所以一定是不同的实例。结果仍然符合预期,这是为什么呢?

因为List内部并不是通过==判断两个元素是否相等,而是使用equals()方法判断两个元素是否相等,例如contains()方法可以实现如下:

1
2
3
4
5
6
7
8
9
10
11
public class ArrayList {
Object[] elementData;
public boolean contains(Object o) {
for (int i = 0; i < size; i++) {
if (o.equals(elementData[i])) {
return true;
}
}
return false;
}
}

因此,要正确使用Listcontains()indexOf()这些方法,放入的实例必须正确覆写equals()方法,否则,放进去的实例,查找不到。我们之所以能正常放入StringInteger这些对象,是因为Java标准库定义的这些类已经正确实现了equals()方法。

我们以Person对象为例,测试一下:

1
import java.util.List;

Run

false

不出意外,虽然放入了new Person("Bob"),但是用另一个new Person("Bob")查询不到,原因就是Person类没有覆写equals()方法。

编写equals

如何正确编写equals()方法?equals()方法要求我们必须满足以下条件:

  • 自反性(Reflexive):对于非nullx来说,x.equals(x)必须返回true
  • 对称性(Symmetric):对于非nullxy来说,如果x.equals(y)true,则y.equals(x)也必须为true
  • 传递性(Transitive):对于非nullxyz来说,如果x.equals(y)truey.equals(z)也为true,那么x.equals(z)也必须为true
  • 一致性(Consistent):对于非nullxy来说,只要xy状态不变,则x.equals(y)总是一致地返回true或者false
  • null的比较:即x.equals(null)永远返回false

上述规则看上去似乎非常复杂,但其实代码实现equals()方法是很简单的,我们以Person类为例:

1
2
3
4
public class Person {
public String name;
public int age;
}

首先,我们要定义“相等”的逻辑含义。对于Person类,如果name相等,并且age相等,我们就认为两个Person实例相等。

因此,编写equals()方法如下:

1
2
3
4
5
6
7
public boolean equals(Object o) {
if (o instanceof Person) {
Person p = (Person) o;
return this.name.equals(p.name) && this.age == p.age;
}
return false;
}

对于引用字段比较,我们使用equals(),对于基本类型字段的比较,我们使用==

如果this.namenull,那么equals()方法会报错,因此,需要继续改写如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean equals(Object o) {
if (o instanceof Person) {
Person p = (Person) o;
boolean nameEquals = false;
if (this.name == null && p.name == null) {
nameEquals = true;
}
if (this.name != null) {
nameEquals = this.name.equals(p.name);
}
return nameEquals && this.age == p.age;
}
return false;
}

如果Person有好几个引用类型的字段,上面的写法就太复杂了。要简化引用类型的比较,我们使用Objects.equals()静态方法:

1
2
3
4
5
6
7
public boolean equals(Object o) {
if (o instanceof Person) {
Person p = (Person) o;
return Objects.equals(this.name, p.name) && this.age == p.age;
}
return false;
}

因此,我们总结一下equals()方法的正确编写方法:

  1. 先确定实例“相等”的逻辑,即哪些字段相等,就认为实例相等;
  2. instanceof判断传入的待比较的Object是不是当前类型,如果是,继续比较,否则,返回false
  3. 对引用类型用Objects.equals()比较,对基本类型直接用==比较。

使用Objects.equals()比较两个引用类型是否相等的目的是省去了判断null的麻烦。两个引用类型都是null时它们也是相等的。

如果不调用Listcontains()indexOf()这些方法,那么放入的元素就不需要实现equals()方法。

小结

List中查找元素时,List的实现类通过元素的equals()方法比较两个元素是否相等,因此,放入的元素必须正确覆写equals()方法,Java标准库提供的StringInteger等已经覆写了equals()方法;

编写equals()方法可借助Objects.equals()判断。

如果不在List中查找元素,就不必覆写equals()方法。


本文整理自

使用List

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!


什么是集合

什么是集合(Collection)?集合就是“由若干个确定的元素所构成的整体”。

在数学中,我们经常遇到集合的概念。例如:

  • 有限集合:
    • 一个班所有的同学构成的集合;
    • 一个网站所有的商品构成的集合;
  • 无限集合:
    • 全体自然数集合:1,2,3,……
    • 有理数集合;
    • 实数集合;

为什么要在计算机中引入集合呢?这是为了便于处理一组类似的数据,例如:

  • 计算所有同学的总成绩和平均成绩;
  • 列举所有的商品名称和价格;
  • ……

在Java中,如果一个Java对象可以在内部持有若干其他Java对象,并对外提供访问接口,我们把这种Java对象称为集合。很显然,Java的数组可以看作是一种集合:

1
2
3
String[] ss = new String[10]; // 可以持有10个String对象
ss[0] = "Hello"; // 可以放入String对象
String first = ss[0]; // 可以获取String对象

既然Java提供了数组这种数据类型,可以充当集合,那么,我们为什么还需要其他集合类?这是因为数组有如下限制:

  • 数组初始化后大小不可变;
  • 数组只能按索引顺序存取。

因此,我们需要各种不同类型的集合类来处理不同的数据,例如:

  • 可变大小的顺序链表;
  • 保证无重复元素的集合;

Collection

Java标准库自带的java.util包提供了集合类:Collection,它是Map外所有其他集合类的根接口。Java的java.util包主要提供了以下三种类型的集合:

  • List:一种有序列表的集合,例如,按索引排列的StudentList
  • Set:一种保证没有重复元素的集合,例如,所有无重复名称的StudentSet
  • Map:一种通过键值(key-value)查找的映射表集合,例如,根据Studentname查找对应StudentMap

Java集合的设计有几个特点:一是实现了接口和实现类相分离,例如,有序表的接口是List,具体的实现类有ArrayListLinkedList等,二是支持泛型,我们可以限制在一个集合中只能放入同一种数据类型的元素,例如:

1
List<String> list = new ArrayList<>(); // 只能放入String类型

最后,Java访问集合总是通过统一的方式——迭代器(Iterator)来实现,它最明显的好处在于无需知道集合内部元素是按什么方式存储的。

由于Java的集合设计非常久远,中间经历过大规模改进,我们要注意到有一小部分集合类是遗留类,不应该继续使用:

  • Hashtable:一种线程安全的Map实现;
  • Vector:一种线程安全的List实现;
  • Stack:基于Vector实现的LIFO的栈。

还有一小部分接口是遗留接口,也不应该继续使用:

  • Enumeration:已被Iterator取代。

小结

Java的集合类定义在java.util包中,支持泛型,主要提供了3种集合类,包括ListSetMap。Java集合使用统一的Iterator遍历,尽量不要使用遗留接口。

迭代器Iterator

Java的集合类都可以使用for each循环,ListSetQueue会迭代每个元素,Map会迭代每个key。以List为例:

1
2
3
4
List<String> list = List.of("Apple", "Orange", "Pear");
for (String s : list) {
System.out.println(s);
}

实际上,Java编译器并不知道如何遍历List。上述代码能够编译通过,只是因为编译器把for each循环通过Iterator改写为了普通的for循环

1
2
3
4
for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
String s = it.next();
System.out.println(s);
}

我们把这种通过Iterator对象遍历集合的模式称为迭代器。

使用迭代器的好处在于,调用方总是以统一的方式遍历各种集合类型,而不必关系它们内部的存储结构。

例如,我们虽然知道ArrayList在内部是以数组形式存储元素,并且,它还提供了get(int)方法。虽然我们可以用for循环遍历:

1
2
3
for (int i=0; i<list.size(); i++) {
Object value = list.get(i);
}

但是这样一来,调用方就必须知道集合的内部存储结构。并且,如果把ArrayList换成LinkedListget(int)方法耗时会随着index的增加而增加。如果把ArrayList换成Set,上述代码就无法编译,因为Set内部没有索引。

Iterator遍历就没有上述问题,因为Iterator对象是集合对象自己在内部创建的,它自己知道如何高效遍历内部的数据集合,调用方则获得了统一的代码,编译器才能把标准的for each循环自动转换为Iterator遍历。

如果我们自己编写了一个集合类,想要使用for each循环,只需满足以下条件:

  • 集合类实现Iterable接口,该接口要求返回一个Iterator对象;
  • Iterator对象迭代集合内部数据。

这里的关键在于,集合类通过调用iterator()方法,返回一个Iterator对象,这个对象必须自己知道如何遍历该集合。

一个简单的Iterator示例如下,它总是以倒序遍历集合:

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
import java.util.*;

public class Main {
public static void main(String[] args) {
ReverseList<String> rlist = new ReverseList<>();
rlist.add("Apple");
rlist.add("Orange");
rlist.add("Pear");
for (String s : rlist) {
System.out.println(s);
}
}
}

class ReverseList<T> implements Iterable<T> {

private List<T> list = new ArrayList<>();

public void add(T t) {
list.add(t);
}

@Override
public Iterator<T> iterator() {
return new ReverseIterator(list.size());
}

class ReverseIterator implements Iterator<T> {
int index;

ReverseIterator(int index) {
this.index = index;
}

@Override
public boolean hasNext() {
return index > 0;
}

@Override
public T next() {
index--;
return ReverseList.this.list.get(index);
}
}
}

虽然ReverseListReverseIterator的实现类稍微比较复杂,但是,注意到这是底层集合库,只需编写一次。而调用方则完全按for each循环编写代码,根本不需要知道集合内部的存储逻辑和遍历逻辑。

在编写Iterator的时候,我们通常可以用一个内部类来实现Iterator接口,这个内部类可以直接访问对应的外部类的所有字段和方法。例如,上述代码中,内部类ReverseIterator可以用ReverseList.this获得当前外部类的this引用,然后,通过这个this引用就可以访问ReverseList的所有字段和方法。

小结

Iterator是一种抽象的数据访问模型。使用Iterator模式进行迭代的好处有:

  • 对任何集合都采用同一种访问模型;
  • 调用者对集合内部结构一无所知;
  • 集合类返回的Iterator对象知道如何迭代。

Java提供了标准的迭代器模型,即集合类实现java.util.Iterable接口,返回java.util.Iterator实例。

工具类Collections

Collections是JDK提供的工具类,同样位于java.util包中。它提供了一系列静态方法,能更方便地操作各种集合。

注意Collections结尾多了一个s,不是Collection!

我们一般看方法名和参数就可以确认Collections提供的该方法的功能。例如,对于以下静态方法:

1
public static boolean addAll(Collection<? super T> c, T... elements) { ... }

addAll()方法可以给一个Collection类型的集合添加若干元素。因为方法签名是Collection,所以我们可以传入ListSet等各种集合类型。

创建空集合

Collections提供了一系列方法来创建空集合:

  • 创建空List:List emptyList()
  • 创建空Map:Map emptyMap()
  • 创建空Set:Set emptySet()

要注意到返回的空集合是不可变集合,无法向其中添加或删除元素。

此外,也可以用各个集合接口提供的of(T...)方法创建空集合。例如,以下创建空List的两个方法是等价的:

1
2
List<String> list1 = List.of();
List<String> list2 = Collections.emptyList();

创建单元素集合

Collections提供了一系列方法来创建一个单元素集合:

  • 创建一个元素的List:List singletonList(T o)
  • 创建一个元素的Map:Map singletonMap(K key, V value)
  • 创建一个元素的Set:Set singleton(T o)

要注意到返回的单元素集合也是不可变集合,无法向其中添加或删除元素。

此外,也可以用各个集合接口提供的of(T...)方法创建单元素集合。例如,以下创建单元素List的两个方法是等价的:

1
2
List<String> list1 = List.of("apple");
List<String> list2 = Collections.singletonList("apple");

实际上,使用List.of(T...)更方便,因为它既可以创建空集合,也可以创建单元素集合,还可以创建任意个元素的集合:

1
2
3
4
List<String> list1 = List.of(); // empty list
List<String> list2 = List.of("apple"); // 1 element
List<String> list3 = List.of("apple", "pear"); // 2 elements
List<String> list4 = List.of("apple", "pear", "orange"); // 3 elements

排序

Collections可以对List进行排序。因为排序会直接修改List元素的位置,因此必须传入可变List

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Main {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("apple");
list.add("pear");
list.add("orange");
// 排序前:
System.out.println(list);
Collections.sort(list);
// 排序后:
System.out.println(list);
}
}

洗牌

Collections提供了洗牌算法,即传入一个有序的List,可以随机打乱List内部元素的顺序,效果相当于让计算机洗牌:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i=0; i<10; i++) {
list.add(i);
}
// 洗牌前:
System.out.println(list);
Collections.shuffle(list);
// 洗牌后:
System.out.println(list);
}
}

不可变集合

Collections还提供了一组方法把可变集合封装成不可变集合:

  • 封装成不可变List:List unmodifiableList(List list)
  • 封装成不可变Set:Set unmodifiableSet(Set set)
  • 封装成不可变Map:Map unmodifiableMap(Map m)

这种封装实际上是通过创建一个代理对象,拦截掉所有修改方法实现的。我们来看看效果:

1
2
3
4
5
6
7
8
9
10
public class Main {
public static void main(String[] args) {
List<String> mutable = new ArrayList<>();
mutable.add("apple");
mutable.add("pear");
// 变为不可变集合:
List<String> immutable = Collections.unmodifiableList(mutable);
immutable.add("orange"); // UnsupportedOperationException!
}
}

然而,继续对原始的可变List进行增删是可以的,并且,会直接影响到封装后的“不可变”List

1
2
3
4
5
6
7
8
9
10
11
public class Main {
public static void main(String[] args) {
List<String> mutable = new ArrayList<>();
mutable.add("apple");
mutable.add("pear");
// 变为不可变集合:
List<String> immutable = Collections.unmodifiableList(mutable);
mutable.add("orange");
System.out.println(immutable);
}
}

输出为

1
[apple, pear, orange]

因此,如果我们希望把一个可变List封装成不可变List,那么,返回不可变List后,最好立刻扔掉可变List的引用,这样可以保证后续操作不会意外改变原始对象,从而造成“不可变”List变化了:

1
2
3
4
5
6
7
8
9
10
11
12
public class Main {
public static void main(String[] args) {
List<String> mutable = new ArrayList<>();
mutable.add("apple");
mutable.add("pear");
// 变为不可变集合:
List<String> immutable = Collections.unmodifiableList(mutable);
// 立刻扔掉mutable的引用:
mutable = null;
System.out.println(immutable);
}
}

线程安全集合

Collections还提供了一组方法,可以把线程不安全的集合变为线程安全的集合:

  • 变为线程安全的List:List synchronizedList(List list)
  • 变为线程安全的Set:Set synchronizedSet(Set s)
  • 变为线程安全的Map:Map synchronizedMap(Map m)

多线程的概念我们会在后面讲。因为从Java 5开始,引入了更高效的并发集合类,所以上述这几个同步方法已经没有什么用了。

小结

Collections类提供了一组工具方法来方便使用集合类:

  • 创建空集合;
  • 创建单元素集合;
  • 创建不可变集合;
  • 排序/洗牌等操作。

本文整理自

Java集合简介

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!


基础

何为心跳

顾名思义, 所谓 心跳, 即在 TCP 长连接中, 客户端和服务器之间定期发送的一种特殊的数据包, 通知对方自己还在线, 以确保 TCP 连接的有效性.

为什么需要心跳

因为网络的不可靠性, 有可能在 TCP 保持长连接的过程中, 由于某些突发情况, 例如网线被拔出, 突然掉电等, 会造成服务器和客户端的连接中断. 在这些突发情况下, 如果恰好服务器和客户端之间没有交互的话, 那么它们是不能在短时间内发现对方已经掉线的. 为了解决这个问题, 我们就需要引入 心跳 机制. 心跳机制的工作原理是: 在服务器和客户端之间一定时间内没有数据交互时, 即处于 idle 状态时, 客户端或服务器会发送一个特殊的数据包给对方, 当接收方收到这个数据报文后, 也立即发送一个特殊的数据报文, 回应发送方, 此即一个 PING-PONG 交互. 自然地, 当某一端收到心跳消息后, 就知道了对方仍然在线, 这就确保 TCP 连接的有效性.

如何实现心跳

我们可以通过两种方式实现心跳机制:

  • 使用 TCP 协议层面的 keepalive 机制.
  • 在应用层上实现自定义的心跳机制.

虽然在 TCP 协议层面上, 提供了 keepalive 保活机制, 但是使用它有几个缺点:

  1. 它不是 TCP 的标准协议, 并且是默认关闭的.
  2. TCP keepalive 机制依赖于操作系统的实现, 默认的 keepalive 心跳时间是 两个小时, 并且对 keepalive 的修改需要系统调用(或者修改系统配置), 灵活性不够.
  3. TCP keepalive 与 TCP 协议绑定, 因此如果需要更换为 UDP 协议时, keepalive 机制就失效了.

虽然使用 TCP 层面的 keepalive 机制比自定义的应用层心跳机制节省流量, 但是基于上面的几点缺点, 一般的实践中, 人们大多数都是选择在应用层上实现自定义的心跳.
既然如此, 那么我们就来大致看看在在 Netty 中是怎么实现心跳的吧. 在 Netty 中, 实现心跳机制的关键是 IdleStateHandler, 它可以对一个 Channel 的 读/写设置定时器, 当 Channel 在一定事件间隔内没有数据交互时(即处于 idle 状态), 就会触发指定的事件.

使用 Netty 实现心跳

上面我们提到了, 在 Netty 中, 实现心跳机制的关键是 IdleStateHandler, 那么这个 Handler 如何使用呢? 我们来看看它的构造器:

1
2
3
public IdleStateHandler(int readerIdleTimeSeconds, int writerIdleTimeSeconds, int allIdleTimeSeconds) {
this((long)readerIdleTimeSeconds, (long)writerIdleTimeSeconds, (long)allIdleTimeSeconds, TimeUnit.SECONDS);
}

实例化一个 IdleStateHandler 需要提供三个参数:

  • readerIdleTimeSeconds, 读超时. 即当在指定的时间间隔内没有从 Channel 读取到数据时, 会触发一个 READER_IDLE 的 IdleStateEvent 事件.
  • writerIdleTimeSeconds, 写超时. 即当在指定的时间间隔内没有数据写入到 Channel 时, 会触发一个 WRITER_IDLE 的 IdleStateEvent 事件.
  • allIdleTimeSeconds, 读/写超时. 即当在指定的时间间隔内没有读或写操作时, 会触发一个 ALL_IDLE 的 IdleStateEvent 事件.

为了展示具体的 IdleStateHandler 实现的心跳机制, 下面我们来构造一个具体的EchoServer 的例子, 这个例子的行为如下:

  1. 在这个例子中, 客户端和服务器通过 TCP 长连接进行通信.
  2. TCP 通信的报文格式是:
1
2
3
4
+--------+-----+---------------+ 
| Length |Type | Content |
| 17 | 1 |"HELLO, WORLD" |
+--------+-----+---------------+
  1. 客户端每隔一个随机的时间后, 向服务器发送消息, 服务器收到消息后, 立即将收到的消息原封不动地回复给客户端.
  2. 若客户端在指定的时间间隔内没有读/写操作, 则客户端会自动向服务器发送一个 PING 心跳, 服务器收到 PING 心跳消息时, 需要回复一个 PONG 消息.

下面所使用的代码例子可以在我的 Github github.com/yongshun/some_java_code 上找到.

通用部分

根据上面定义的行为, 我们接下来实现心跳的通用部分 CustomHeartbeatHandler:

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
/**
* @author xiongyongshun
* @version 1.0
* @email yongshun1228@gmail.com
* @created 16/9/18 13:02
*/
public abstract class CustomHeartbeatHandler extends SimpleChannelInboundHandler<ByteBuf> {
public static final byte PING_MSG = 1;
public static final byte PONG_MSG = 2;
public static final byte CUSTOM_MSG = 3;
protected String name;
private int heartbeatCount = 0;

public CustomHeartbeatHandler(String name) {
this.name = name;
}

@Override
protected void channelRead0(ChannelHandlerContext context, ByteBuf byteBuf) throws Exception {
if (byteBuf.getByte(4) == PING_MSG) {
sendPongMsg(context);
} else if (byteBuf.getByte(4) == PONG_MSG){
System.out.println(name + " get pong msg from " + context.channel().remoteAddress());
} else {
handleData(context, byteBuf);
}
}

protected void sendPingMsg(ChannelHandlerContext context) {
ByteBuf buf = context.alloc().buffer(5);
buf.writeInt(5);
buf.writeByte(PING_MSG);
context.writeAndFlush(buf);
heartbeatCount++;
System.out.println(name + " sent ping msg to " + context.channel().remoteAddress() + ", count: " + heartbeatCount);
}

private void sendPongMsg(ChannelHandlerContext context) {
ByteBuf buf = context.alloc().buffer(5);
buf.writeInt(5);
buf.writeByte(PONG_MSG);
context.channel().writeAndFlush(buf);
heartbeatCount++;
System.out.println(name + " sent pong msg to " + context.channel().remoteAddress() + ", count: " + heartbeatCount);
}

protected abstract void handleData(ChannelHandlerContext channelHandlerContext, ByteBuf byteBuf);

@Override
public void userEventTriggered(ChannelHandlerContext ctx, Object evt) throws Exception {
// IdleStateHandler 所产生的 IdleStateEvent 的处理逻辑.
if (evt instanceof IdleStateEvent) {
IdleStateEvent e = (IdleStateEvent) evt;
switch (e.state()) {
case READER_IDLE:
handleReaderIdle(ctx);
break;
case WRITER_IDLE:
handleWriterIdle(ctx);
break;
case ALL_IDLE:
handleAllIdle(ctx);
break;
default:
break;
}
}
}

@Override
public void channelActive(ChannelHandlerContext ctx) throws Exception {
System.err.println("---" + ctx.channel().remoteAddress() + " is active---");
}

@Override
public void channelInactive(ChannelHandlerContext ctx) throws Exception {
System.err.println("---" + ctx.channel().remoteAddress() + " is inactive---");
}

protected void handleReaderIdle(ChannelHandlerContext ctx) {
System.err.println("---READER_IDLE---");
}

protected void handleWriterIdle(ChannelHandlerContext ctx) {
System.err.println("---WRITER_IDLE---");
}

protected void handleAllIdle(ChannelHandlerContext ctx) {
System.err.println("---ALL_IDLE---");
}
}

类 CustomHeartbeatHandler 负责心跳的发送和接收, 我们接下来详细地分析一下它的作用. 我们在前面提到, IdleStateHandler 是实现心跳的关键, 它会根据不同的 IO idle 类型来产生不同的 IdleStateEvent 事件, 而这个事件的捕获, 其实就是在 userEventTriggered 方法中实现的.
我们来看看 CustomHeartbeatHandler.userEventTriggered 的具体实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@Override
public void userEventTriggered(ChannelHandlerContext ctx, Object evt) throws Exception {
if (evt instanceof IdleStateEvent) {
IdleStateEvent e = (IdleStateEvent) evt;
switch (e.state()) {
case READER_IDLE:
handleReaderIdle(ctx);
break;
case WRITER_IDLE:
handleWriterIdle(ctx);
break;
case ALL_IDLE:
handleAllIdle(ctx);
break;
default:
break;
}
}
}

在 userEventTriggered 中, 根据 IdleStateEvent 的 state() 的不同, 而进行不同的处理. 例如如果是读取数据 idle, 则 e.state() == READER_IDLE, 因此就调用 handleReaderIdle 来处理它. CustomHeartbeatHandler 提供了三个 idle 处理方法: handleReaderIdle, handleWriterIdle, handleAllIdle, 这三个方法目前只有默认的实现, 它需要在子类中进行重写, 现在我们暂时略过它们, 在具体的客户端和服务器的实现部分时再来看它们.

知道了这一点后, 我们接下来看看数据处理部分:

1
2
3
4
5
6
7
8
9
10
@Override
protected void channelRead0(ChannelHandlerContext context, ByteBuf byteBuf) throws Exception {
if (byteBuf.getByte(4) == PING_MSG) {
sendPongMsg(context);
} else if (byteBuf.getByte(4) == PONG_MSG){
System.out.println(name + " get pong msg from " + context.channel().remoteAddress());
} else {
handleData(context, byteBuf);
}
}

在 CustomHeartbeatHandler.channelRead0 中, 我们首先根据报文协议:

1
2
3
4
+--------+-----+---------------+ 
| Length |Type | Content |
| 17 | 1 |"HELLO, WORLD" |
+--------+-----+---------------+

来判断当前的报文类型, 如果是 PING_MSG 则表示是服务器收到客户端的 PING 消息, 此时服务器需要回复一个 PONG 消息, 其消息类型是 PONG_MSG.
扔报文类型是 PONG_MSG, 则表示是客户端收到服务器发送的 PONG 消息, 此时打印一个 log 即可.

客户端部分

客户端初始化

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
public class Client {
public static void main(String[] args) {
NioEventLoopGroup workGroup = new NioEventLoopGroup(4);
Random random = new Random(System.currentTimeMillis());
try {
Bootstrap bootstrap = new Bootstrap();
bootstrap
.group(workGroup)
.channel(NioSocketChannel.class)
.handler(new ChannelInitializer<SocketChannel>() {
protected void initChannel(SocketChannel socketChannel) throws Exception {
ChannelPipeline p = socketChannel.pipeline();
p.addLast(new IdleStateHandler(0, 0, 5));
p.addLast(new LengthFieldBasedFrameDecoder(1024, 0, 4, -4, 0));
p.addLast(new ClientHandler());
}
});

Channel ch = bootstrap.remoteAddress("127.0.0.1", 12345).connect().sync().channel();
for (int i = 0; i < 10; i++) {
String content = "client msg " + i;
ByteBuf buf = ch.alloc().buffer();
buf.writeInt(5 + content.getBytes().length);
buf.writeByte(CustomHeartbeatHandler.CUSTOM_MSG);
buf.writeBytes(content.getBytes());
ch.writeAndFlush(buf);

Thread.sleep(random.nextInt(20000));
}
} catch (Exception e) {
throw new RuntimeException(e);
} finally {
workGroup.shutdownGracefully();
}
}
}

上面的代码是 Netty 的客户端端的初始化代码, 使用过 Netty 的朋友对这个代码应该不会陌生. 别的部分我们就不再赘述, 我们来看看 ChannelInitializer.initChannel 部分即可:

1
2
3
4
5
6
7
8
.handler(new ChannelInitializer<SocketChannel>() {
protected void initChannel(SocketChannel socketChannel) throws Exception {
ChannelPipeline p = socketChannel.pipeline();
p.addLast(new IdleStateHandler(0, 0, 5));
p.addLast(new LengthFieldBasedFrameDecoder(1024, 0, 4, -4, 0));
p.addLast(new ClientHandler());
}
});

我们给 pipeline 添加了三个 Handler, IdleStateHandler 这个 handler 是心跳机制的核心, 我们为客户端端设置了读写 idle 超时, 时间间隔是5s, 即如果客户端在间隔 5s 后都没有收到服务器的消息或向服务器发送消息, 则产生 ALL_IDLE 事件.
接下来我们添加了 LengthFieldBasedFrameDecoder, 它是负责解析我们的 TCP 报文, 因为和本文的目的无关, 因此这里不详细展开.
最后一个 Handler 是 ClientHandler, 它继承于 CustomHeartbeatHandler, 是我们处理业务逻辑部分.

客户端 Handler

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class ClientHandler extends CustomHeartbeatHandler {
public ClientHandler() {
super("client");
}

@Override
protected void handleData(ChannelHandlerContext channelHandlerContext, ByteBuf byteBuf) {
byte[] data = new byte[byteBuf.readableBytes() - 5];
byteBuf.skipBytes(5);
byteBuf.readBytes(data);
String content = new String(data);
System.out.println(name + " get content: " + content);
}

@Override
protected void handleAllIdle(ChannelHandlerContext ctx) {
super.handleAllIdle(ctx);
sendPingMsg(ctx);
}
}

ClientHandler 继承于 CustomHeartbeatHandler, 它重写了两个方法, 一个是 handleData, 在这里面实现 仅仅打印收到的消息.
第二个重写的方法是 handleAllIdle. 我们在前面提到, 客户端负责发送心跳的 PING 消息, 当客户端产生一个 ALL_IDLE 事件后, 会导致父类的 CustomHeartbeatHandler.userEventTriggered 调用, 而 userEventTriggered 中会根据 e.state() 来调用不同的方法, 因此最后调用的是 ClientHandler.handleAllIdle, 在这个方法中, 客户端调用 sendPingMsg 向服务器发送一个 PING 消息.

服务器部分

服务器初始化

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
public class Server {
public static void main(String[] args) {
NioEventLoopGroup bossGroup = new NioEventLoopGroup(1);
NioEventLoopGroup workGroup = new NioEventLoopGroup(4);
try {
ServerBootstrap bootstrap = new ServerBootstrap();
bootstrap
.group(bossGroup, workGroup)
.channel(NioServerSocketChannel.class)
.childHandler(new ChannelInitializer<SocketChannel>() {
protected void initChannel(SocketChannel socketChannel) throws Exception {
ChannelPipeline p = socketChannel.pipeline();
p.addLast(new IdleStateHandler(10, 0, 0));
p.addLast(new LengthFieldBasedFrameDecoder(1024, 0, 4, -4, 0));
p.addLast(new ServerHandler());
}
});

Channel ch = bootstrap.bind(12345).sync().channel();
ch.closeFuture().sync();
} catch (Exception e) {
throw new RuntimeException(e);
} finally {
bossGroup.shutdownGracefully();
workGroup.shutdownGracefully();
}
}
}

服务器的初始化部分也没有什么好说的, 它也和客户端的初始化一样, 为 pipeline 添加了三个 Handler.

服务器 Handler

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class ServerHandler extends CustomHeartbeatHandler {
public ServerHandler() {
super("server");
}

@Override
protected void handleData(ChannelHandlerContext channelHandlerContext, ByteBuf buf) {
byte[] data = new byte[buf.readableBytes() - 5];
ByteBuf responseBuf = Unpooled.copiedBuffer(buf);
buf.skipBytes(5);
buf.readBytes(data);
String content = new String(data);
System.out.println(name + " get content: " + content);
channelHandlerContext.write(responseBuf);
}

@Override
protected void handleReaderIdle(ChannelHandlerContext ctx) {
super.handleReaderIdle(ctx);
System.err.println("---client " + ctx.channel().remoteAddress().toString() + " reader timeout, close it---");
ctx.close();
}
}

ServerHandler 继承于 CustomHeartbeatHandler, 它重写了两个方法, 一个是 handleData, 在这里面实现 EchoServer 的功能: 即收到客户端的消息后, 立即原封不动地将消息回复给客户端.
第二个重写的方法是 handleReaderIdle, 因为服务器仅仅对客户端的读 idle 感兴趣, 因此只重新了这个方法. 若服务器在指定时间后没有收到客户端的消息, 则会触发 READER_IDLE 消息, 进而会调用 handleReaderIdle 这个方法. 我们在前面提到, 客户端负责发送心跳的 PING 消息, 并且服务器的 READER_IDLE 的超时时间是客户端发送 PING 消息的间隔的两倍, 因此当服务器 READER_IDLE 触发时, 就可以确定是客户端已经掉线了, 因此服务器直接关闭客户端连接即可.

总结

  1. 使用 Netty 实现心跳机制的关键就是利用 IdleStateHandler 来产生对应的 idle 事件.
  2. 一般是客户端负责发送心跳的 PING 消息, 因此客户端注意关注 ALL_IDLE 事件, 在这个事件触发后, 客户端需要向服务器发送 PING 消息, 告诉服务器”我还存活着”.
  3. 服务器是接收客户端的 PING 消息的, 因此服务器关注的是 READER_IDLE 事件, 并且服务器的 READER_IDLE 间隔需要比客户端的 ALL_IDLE 事件间隔大(例如客户端ALL_IDLE 是5s 没有读写时触发, 因此服务器的 READER_IDLE 可以设置为10s)
  4. 当服务器收到客户端的 PING 消息时, 会发送一个 PONG 消息作为回复. 一个 PING-PONG 消息对就是一个心跳交互.

实现客户端的断线重连

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
public class Client {
private NioEventLoopGroup workGroup = new NioEventLoopGroup(4);
private Channel channel;
private Bootstrap bootstrap;

public static void main(String[] args) throws Exception {
Client client = new Client();
client.start();
client.sendData();
}

public void sendData() throws Exception {
Random random = new Random(System.currentTimeMillis());
for (int i = 0; i < 10000; i++) {
if (channel != null && channel.isActive()) {
String content = "client msg " + i;
ByteBuf buf = channel.alloc().buffer(5 + content.getBytes().length);
buf.writeInt(5 + content.getBytes().length);
buf.writeByte(CustomHeartbeatHandler.CUSTOM_MSG);
buf.writeBytes(content.getBytes());
channel.writeAndFlush(buf);
}

Thread.sleep(random.nextInt(20000));
}
}

public void start() {
try {
bootstrap = new Bootstrap();
bootstrap
.group(workGroup)
.channel(NioSocketChannel.class)
.handler(new ChannelInitializer<SocketChannel>() {
protected void initChannel(SocketChannel socketChannel) throws Exception {
ChannelPipeline p = socketChannel.pipeline();
p.addLast(new IdleStateHandler(0, 0, 5));
p.addLast(new LengthFieldBasedFrameDecoder(1024, 0, 4, -4, 0));
p.addLast(new ClientHandler(Client.this));
}
});
doConnect();

} catch (Exception e) {
throw new RuntimeException(e);
}
}

protected void doConnect() {
if (channel != null && channel.isActive()) {
return;
}

ChannelFuture future = bootstrap.connect("127.0.0.1", 12345);

future.addListener(new ChannelFutureListener() {
public void operationComplete(ChannelFuture futureListener) throws Exception {
if (futureListener.isSuccess()) {
channel = futureListener.channel();
System.out.println("Connect to server successfully!");
} else {
System.out.println("Failed to connect to server, try connect after 10s");

futureListener.channel().eventLoop().schedule(new Runnable() {
@Override
public void run() {
doConnect();
}
}, 10, TimeUnit.SECONDS);
}
}
});
}

}

上面的代码中, 我们抽象出 doConnect 方法, 它负责客户端和服务器的 TCP 连接的建立, 并且当 TCP 连接失败时, doConnect 会 通过 “channel().eventLoop().schedule” 来延时10s 后尝试重新连接.

客户端 Handler

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
public class ClientHandler extends CustomHeartbeatHandler {
private Client client;
public ClientHandler(Client client) {
super("client");
this.client = client;
}

@Override
protected void handleData(ChannelHandlerContext channelHandlerContext, ByteBuf byteBuf) {
byte[] data = new byte[byteBuf.readableBytes() - 5];
byteBuf.skipBytes(5);
byteBuf.readBytes(data);
String content = new String(data);
System.out.println(name + " get content: " + content);
}

@Override
protected void handleAllIdle(ChannelHandlerContext ctx) {
super.handleAllIdle(ctx);
sendPingMsg(ctx);
}

@Override
public void channelInactive(ChannelHandlerContext ctx) throws Exception {
super.channelInactive(ctx);
client.doConnect();
}
}

断线重连的关键一点是检测连接是否已经断开. 因此我们改写了 ClientHandler, 重写了 channelInactive 方法. 当 TCP 连接断开时, 会回调 channelInactive 方法, 因此我们在这个方法中调用 client.doConnect() 来进行重连.

完整代码可以在我的 Github github.com/yongshun/some_java_code 上找到.


本文整理自

[浅析 Netty 实现心跳机制与断线重连]

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!


哈希表(hash table)也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,而HashMap的实现原理也常常出现在各类的面试题中,重要性可见一斑。

本文会对java集合框架中的对应实现HashMap的实现原理进行讲解,然后会对JDK7的HashMap源码进行分析(JDK8会有所不同,需要了解的可自行阅读JDK8的HashMap源码)。

JDK7和JDK8中HashMap的大致变化是:

1.7中采用数组+链表,1.8采用的是数组+链表/红黑树,即在1.7中链表长度超过一定长度后就改成红黑树存储。

1.7扩容时需要重新计算哈希值和索引位置(rehash即开启自适应hash,只对String有效,initHashSeedAsNeeded()方法决定是否重新计算String类型的hash值),1.8并不重新计算哈希值,巧妙地采用和扩容后容量进行&操作来计算新的索引位置。

1.7是采用表头插入法插入链表,1.8采用的是尾部插入法。

在1.7中采用表头插入法,在扩容时会改变链表中元素原本的顺序,以至于在并发场景下导致链表成环的问题;在1.8中采用尾部插入法,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。

目录

  • 什么是哈希表
  • HashMap实现原理
  • 为何HashMap的数组长度一定是2的次幂?
  • 重写equals方法需同时重写hashCode方法
  • 总结

一、什么是哈希表

在讨论哈希表之前,我们先大概了解下其他数据结构在新增,查找等基础操作执行性能

数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O(n),当然,对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查找复杂度提高为O(logn);对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n)

线性链表:对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行比对,复杂度为O(n)

二叉树:对一棵相对平衡的有序二叉树,对其进行插入,查找,删除等操作,平均复杂度均为O(logn)。

哈希表:相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下,仅需一次定位即可完成,时间复杂度为O(1),接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。

我们知道,数据结构的物理存储结构只有两种:顺序存储结构和链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而在上面我们提到过,在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组

比如我们要新增或查找某个元素,我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置,通过数组下标一次定位就可完成操作。

存储位置 = f(关键字)

其中,这个函数f一般称为哈希函数,这个函数的设计好坏会直接影响到哈希表的优劣。举个例子,比如我们要在哈希表中执行插入操作:

img

查找操作同理,先通过哈希函数计算出实际存储地址,然后从数组中对应地址取出即可。

哈希冲突

然而万事无完美,如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。

前面我们提到过,哈希函数的设计至关重要,好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。

那么哈希冲突如何解决呢?哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法,而HashMap即是采用了链地址法,也就是数组+链表的方式,

二、HashMap实现原理

HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。

1
2
//HashMap的主干数组,可以看到就是一个Entry数组,初始值为空数组{},主干数组的长度一定是2的次幂,至于为什么这么做,后面会有详细分析。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

Entry是HashMap中的一个静态内部类。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存储指向下一个Entry的引用,单链表结构
int hash;//对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算

/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}

所以,HashMap的整体结构如下

img

简单来说,HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。

其他几个重要字段

1
2
3
4
5
6
7
8
//实际存储的key-value键值对的个数
transient int size;
//阈值,当table == {}时,该值为初始容量(初始容量默认为16);当table被填充了,也就是为table分配内存空间后,threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold,后面会详细谈到
int threshold;
//负载因子,代表了table的填充度有多少,默认是0.75
final float loadFactor;
//用于快速失败,由于HashMap非线程安全,在对HashMap进行迭代时,如果期间其他线程的参与导致HashMap的结构发生变化了(比如put,remove等操作),需要抛出异常ConcurrentModificationException
transient int modCount;

HashMap有4个构造器,其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数,会使用默认值

initialCapacity默认为16,loadFactory默认为0.75

我们看下其中一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public HashMap(int initialCapacity, float loadFactor) {
     //此处对传入的初始容量进行校验,最大不能超过MAXIMUM_CAPACITY = 1<<30(230)
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;
threshold = initialCapacity;
     
init();//init方法在HashMap中没有实际实现,不过在其子类如 linkedHashMap中就会有对应实现
}

从上面这段代码我们可以看出,在常规构造器中,没有为数组table分配内存空间(有一个入参为指定Map的构造器例外),而是在执行put操作的时候才真正构建table数组

OK,接下来我们来看看put操作的实现吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public V put(K key, V value) {
//如果table数组为空数组{},进行数组填充(为table分配实际内存空间),入参为threshold,此时threshold为initialCapacity 默认是1<<4(24=16)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//如果key为null,存储位置为table[0]或table[0]的冲突链上
if (key == null)
return putForNullKey(value);
int hash = hash(key);//对key的hashcode进一步计算,确保散列均匀
int i = indexFor(hash, table.length);//获取在table中的实际位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果该对应数据已存在,执行覆盖操作。用新value替换旧value,并返回旧value
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;//保证并发访问时,若HashMap内部结构发生变化,快速响应失败
addEntry(hash, key, value, i);//新增一个entry
return null;
}

先来看看inflateTable这个方法

1
2
3
4
5
6
private void inflateTable(int toSize) {
int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//此处为threshold赋值,取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值,capaticy一定不会超过MAXIMUM_CAPACITY,除非loadFactor大于1
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}

inflateTable这个方法用于为主干数组table在内存中分配存储空间,通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂,比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.

1
2
3
4
5
6
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂,Integer.highestOneBit是用来获取最左边的bit(其他bit位为0)所代表的数值.

hash函数

1
2
3
4
5
6
7
8
9
10
11
12
//这是一个神奇的函数,用了很多的异或,移位等运算,对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}

h ^= k.hashCode();

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

以上hash函数计算出的值,通过indexFor进一步处理来获取实际的存储位置

1
2
3
4
5
6
/**
* 返回数组下标
*/
static int indexFor(int h, int length) {
return h & (length-1);
}

h&(length-1)保证获取的index一定在数组范围内,举个例子,默认容量16,length-1=15,h=18,转换成二进制计算为

1
2
3
4
    1  0  0  1  0
& 0 1 1 1 1
__________________
0 0 0 1 0 = 2

最终计算出的index=2。有些版本的对于此处的计算会使用 取模运算,也能保证index一定在数组范围内,不过位运算对计算机来说,性能更高一些(HashMap中有大量位运算)

所以最终存储位置的确定流程是这样的:

img

再来看看addEntry的实现:

1
2
3
4
5
6
7
8
9
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//当size超过临界阈值threshold,并且即将发生哈希冲突时进行扩容
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}

createEntry(hash, key, value, bucketIndex);
}

通过以上代码能够得知,当发生哈希冲突并且size大于阈值的时候,需要进行数组扩容,扩容时,需要新建一个长度为之前数组2倍的新的数组,然后将当前的Entry数组中的元素全部传输过去,扩容后的新数组长度为之前的2倍,所以扩容相对来说是个耗资源的操作。

三、为何HashMap的数组长度一定是2的次幂?

我们来继续看上面提到的resize方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}

Entry[] newTable = new Entry[newCapacity];
//rehash即开启自适应hash,只对String有效,`initHashSeedAsNeeded()`方法决定是否重新计算String类型的hash值
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

如果数组进行扩容,数组长度发生变化,而存储位置 index = h&(length-1),index也可能会发生变化,需要重新计算index,我们先来看看transfer这个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
     //for循环中的代码,逐个遍历链表,重新计算索引位置,将老数组数据复制到新数组中去(数组不存储实际数据,所以仅仅是拷贝引用而已)
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
          //将当前entry的next链指向新的索引位置,newTable[i]有可能为空,有可能也是个entry链,如果是entry链,直接在链表头部插入。
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}

这个方法将老数组中的数据逐个链表地遍历,扔到新的扩容后的数组中,我们的数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后,再通过和 length-1进行位运算得到最终数组索引位置。

hashMap的数组长度一定保持2的次幂,比如16的二进制表示为 10000,那么length-1就是15,二进制为01111,同理扩容后的数组长度为32,二进制表示为100000,length-1为31,二进制表示为011111。

从下图可以我们也能看到这样会保证低位全为1,而扩容后只有一位差异,也就是多出了最左位的1,这样在通过 h&(length-1)的时候,只要h对应的最左边的那一个差异位为0,就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换),个人理解。

img

还有,数组长度保持2的次幂,length-1的低位都为1,会使得获得的数组索引index更加均匀,比如:

img

我们看到,上面的&运算,高位是不会对结果产生影响的(hash函数采用各种位运算可能也是为了使得低位更加散列),我们只关注低位bit,如果低位全部为1,那么对于h低位部分来说,任何一位的变化都会对结果产生影响,也就是说,要得到index=21这个存储位置,h的低位只有这一种组合。这也是数组长度设计为必须为2的次幂的原因。

img

如果不是2的次幂,也就是低位不是全为1此时,要使得index=21,h的低位部分不再具有唯一性了,哈希冲突的几率会变的更大,同时,index对应的这个bit位无论如何不会等于1了,而对应的那些数组位置也就被白白浪费了。

get方法

1
2
3
4
5
6
7
public V get(Object key) {
     //如果key为null,则直接去table[0]处去检索即可。
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}

get方法通过key值返回对应value,如果key为null,直接去table[0]处检索。我们再看一下getEntry这个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
final Entry<K,V> getEntry(Object key) {

if (size == 0) {
return null;
}
//通过key的hashcode值计算hash值
int hash = (key == null) ? 0 : hash(key);
//indexFor (hash&length-1) 获取最终数组索引,然后遍历链表,通过equals方法比对找出对应记录
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}

可以看出,get方法的实现相对简单,key(hashcode)–>hash–>indexFor–>最终索引位置,找到对应位置table[i],再查看是否有链表,遍历链表,通过key的equals方法比对查找对应的记录。要注意的是,有人觉得上面在定位到数组位置之后然后遍历链表的时候,e.hash == hash这个判断没必要,仅通过equals判断就可以。

其实不然,试想一下,如果传入的key对象重写了equals方法却没有重写hashCode,而恰巧此对象定位到这个数组位置,如果仅仅用equals判断可能是相等的,但其hashCode和当前对象不一致,这种情况,根据Object的hashCode的约定,不能返回当前对象,而应该返回null,后面的例子会做出进一步解释。

四、重写equals方法需同时重写hashCode方法

关于HashMap的源码分析就介绍到这儿了,最后我们再聊聊老生常谈的一个问题,各种资料上都会提到,“重写equals时也要同时覆盖hashcode”,我们举个小例子来看看,如果重写了equals而不重写hashcode会发生什么样的问题

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
/**
* Created by chengxiao on 2016/11/15.
*/
public class MyTest {
private static class Person{
int idCard;
String name;

public Person(int idCard, String name) {
this.idCard = idCard;
this.name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()){
return false;
}
Person person = (Person) o;
//两个对象是否等值,通过idCard来确定
return this.idCard == person.idCard;
}

}
public static void main(String []args){
HashMap<Person,String> map = new HashMap<Person, String>();
Person person = new Person(1234,"乔峰");
//put到hashmap中去
map.put(person,"天龙八部");
//get取出,从逻辑上讲应该能输出“天龙八部”
System.out.println("结果:"+map.get(new Person(1234,"萧峰")));
}
}

实际输出结果:

结果:null

如果我们已经对HashMap的原理有了一定了解,这个结果就不难理解了。尽管我们在进行get和put操作的时候,使用的key从逻辑上讲是等值的(通过equals比较是相等的),但由于没有重写hashCode方法,所以put操作时,key(hashcode1)–>hash–>indexFor–>最终索引位置 ,而通过key取出value的时候 key(hashcode1)–>hash–>indexFor–>最终索引位置,由于hashcode1不等于hashcode2,导致没有定位到一个数组位置而返回逻辑上错误的值null(也有可能碰巧定位到一个数组位置,但是也会判断其entry的hash值是否相等,上面get方法中有提到。)

所以,在重写equals的方法的时候,必须注意重写hashCode方法,同时还要保证通过equals判断相等的两个对象,调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象,其hashCode可以相同(只不过会发生哈希冲突,应尽量避免)。

五、总结

本文描述了HashMap的实现原理,并结合源码做了进一步的分析,也涉及到一些源码细节设计缘由,最后简单介绍了为什么重写equals的时候需要重写hashCode方法。


本文整理自

HashMap的实现原理

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!


在Integer类中有这么一个方法,你可以给它传入一个数字,它将返回小于等于这个数字的一个2的幂次方数。这个方法就是highestOneBit(int i)

比如下面的Demo,注意方法的输入与返回值:

1
2
3
System.out.println(Integer.highestOneBit(15));  // 输出8
System.out.println(Integer.highestOneBit(16)); // 输出16
System.out.println(Integer.highestOneBit(17)); // 输出16

首先,对于这个方法的功能:给定一个数字,找到小于或等于这个数字的一个2的幂次方数。

如果我们要自己来实现的话,我们需要知道:怎么判断一个数字是2的幂次方数。

说真的,我一下想不到什么好方法来判断,唯一能想到的就是一个数字如果把它转换成二进制表示的话,它会有一个规律:如果一个数字是2的幂次方数,那么它对应的二进制表示仅有一个bit位上是1,其他bit位全为0。 比如: 十进制6,二进制表示为:0000 0110 十进制8,二进制表示为:0000 1000 十进制9,二进制表示为:0000 1001 所以,我们可以利用一个数字的二进制表示来判断这个数字是不是2的幂次方数。关键代码怎么实现呢?去遍历每个bit位?可以,但是不好,那怎么办?我们还是回头仔细看看Integer是如何实现的吧?

1
2
3
4
5
6
7
8
9
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}

我们发现这段代码中没有任何的遍历,只有位运算与一个减法,也就是说它的实现思路和我们自己的实现思路完全不一样,它的思路就是:给定一个数字,通过一系列的运算,得到一个小于或等于该数字的一个2的幂次方数。

也就是:如果给定一个数字18,通过运算后,要得到16。

18用二进制表示为: 0001 0010

想要得到的结果(16)是:0001 0000

那么这个运算的过程无非就是将18对应的二进制数中除最高位的1之外的其他bit位都清零,则拿到了我们想要的结果。

那怎么通过位运算来实现这个过程呢?

我们拿18对应的二进制数0001 0010来举个例子就行了: 先将0001 0010右移1位, 得到0000 1001,再与自身进行或运算: 得到0001 1011

再将0001 1011右移2位, 得到0000 0110,再与自身进行或运算: 得到0001 1111

再将0001 1111右移4位, 得到0000 0001,再与自身进行或运算: 得到0001 1111

再将0001 1111右移8位, 得到0000 0000,再与自身进行或运算: 得到0001 1111

再将0001 1111右移16位, 得到0000 0000,再与自身进行或运算: 得到0001 1111

再将0001 1111无符号右移1位, 得到0000 1111

最后用0001 1111 - 0000 1111 = 0001 0000 震惊!得到了我们想要的结果。

其实这个过程可以抽象成这样: 现在有一个二进制数据,0001****,我们不关心低位的取值情况,我们对其进行右移并且进行或运算。

先将0001****右移1位, 得到00001***,再与自身进行或运算: 得到00011***

再将00011***右移2位, 得到0000011*,再与自身进行或运算: 得到0001111*

再将0001111*右移4位, 得到00000001,再与自身进行或运算: 得到00011111

后面不用再推算了,到这里我们其实可以发现一个规律: 右移与或运算的目的就是想让某个数字的低位都变为1,再用该结果 减去 该结果右移一位后的结果,则相当于清零了原数字的低位。即得到了我们想要的结果。

到此,只能感叹JDK作者对于位运算的使用已经达到了出神入化的境界了。


本文整理自

Integer.highestOneBit(int i)方法的作用与底层实现

仅做个人学习总结所用,遵循CC 4.0 BY-SA版权协议,如有侵权请联系删除!


实现单机的百万连接,瓶颈有以下几点:
1、如何模拟百万连接
2、突破局部文件句柄的限制
3、突破全局文件句柄的限制
在linux系统里面,单个进程打开的句柄数是非常有限的,一条TCP连接就对应一个文件句柄,而对于我们应用程序来说,一个服务端默认建立的连接数是有限制的。

如下图所示,通常一个客户端去除一些被占用的端口之后,可用的端口大于只有6w个左右,要想模拟百万连接要起比较多的客户端,而且比较麻烦,所以这种方案不合适。

img

在服务端启动800~8100,而客户端依旧使用1025-65535范围内可用的端口号,让同一个端口号,可以连接Server的不同端口。这样的话,6W的端口可以连接Server的100个端口,累加起来就能实现近600W左右的连接,TCP是以一个四元组概念,以原IP、原端口号、目的IP、目的端口号来确定的,当原IP 和原端口号相同,但目的端口号不同,最终系统会把他当成两条TCP 连接来处理,所以TCP连接可以如此设计。

img

测试环境

netty客户端和netty服务端,都是springboot项目。
运行环境:linux
netty版本:4.1.6.Final

netty服务端代码

1
2
3
4
5
6
7
8
9
netty maven
<properties>
<netty-all.version>4.1.6.Final</netty-all.version>
</properties>
<dependency>
<groupId>io.netty</groupId>
<artifactId>netty-all</artifactId>
<version>${netty-all.version}</version>
</dependency>
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
93
@SpringBootApplication
public class NettyserverApplication {
private static final int BEGIN_PORT = 8000;
private static final int N_PORT = 100;
public static void main(String[] args) {
SpringApplication.run(NettyserverApplication.class, args);
new Server().start(BEGIN_PORT, N_PORT);
}
}
/----------------------------------------------------------------------------------
import io.netty.bootstrap.ServerBootstrap;
import io.netty.channel.ChannelFutureListener;
import io.netty.channel.ChannelOption;
import io.netty.channel.EventLoopGroup;
import io.netty.channel.nio.NioEventLoopGroup;
import io.netty.channel.socket.nio.NioServerSocketChannel;
public final class Server {
public void start(int beginPort, int nPort) {
System.out.println("server starting....");

EventLoopGroup bossGroup = new NioEventLoopGroup();
EventLoopGroup workerGroup = new NioEventLoopGroup();

ServerBootstrap bootstrap = new ServerBootstrap();
bootstrap.group(bossGroup, workerGroup);
bootstrap.channel(NioServerSocketChannel.class);
bootstrap.childOption(ChannelOption.SO_REUSEADDR, true);

bootstrap.childHandler(new ConnectionCountHandler());

/**
* 绑定100个端口号
*/
for (int i = 0; i < nPort; i++) {
int port = beginPort + i;
bootstrap.bind(port).addListener((ChannelFutureListener) future -> {
System.out.println("bind success in port: " + port);
});
}
System.out.println("server started!");
}
}
/-------------------------------------------------------------------------------------------------
import io.netty.channel.Channel;
import io.netty.channel.ChannelHandler.Sharable;
import io.netty.channel.ChannelHandlerContext;
import io.netty.channel.ChannelInboundHandlerAdapter;

import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;

@Sharable
public class ConnectionCountHandler extends ChannelInboundHandlerAdapter {
//jdk1.5 并发包中的用于计数的类
private AtomicInteger nConnection = new AtomicInteger();

public ConnectionCountHandler() {
/**
* 每两秒统计一下连接数
*/
Executors.newSingleThreadScheduledExecutor().scheduleAtFixedRate(() -> {
System.out.println("connections: " + nConnection.get());
}, 0, 2, TimeUnit.SECONDS);

}
/**
* 每次过来一个新连接就对连接数加一
* @param ctx
*/
@Override
public void channelActive(ChannelHandlerContext ctx) {
nConnection.incrementAndGet();
}
/**
* 端口的时候减一
* @param ctx
*/
@Override
public void channelInactive(ChannelHandlerContext ctx) {
nConnection.decrementAndGet();
}

@Override
public void exceptionCaught(ChannelHandlerContext ctx, Throwable cause) throws Exception {
super.exceptionCaught(ctx, cause);
Channel channel = ctx.channel();
if(channel.isActive()){
ctx.close();
}
//……
}
}

netty客户端代码

1
2
3
4
5
6
7
8
9
netty maven
<properties>
<netty-all.version>4.1.6.Final</netty-all.version>
</properties>
<dependency>
<groupId>io.netty</groupId>
<artifactId>netty-all</artifactId>
<version>${netty-all.version}</version>
</dependency>
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
@SpringBootApplication
public class NettyclientApplication {
private static final int BEGIN_PORT = 8000;
private static final int N_PORT = 100;
public static void main(String[] args) {
SpringApplication.run(NettyclientApplication.class, args);
new Client().start(BEGIN_PORT, N_PORT);
}
}
//----------------------------------------------------------------------------------------
package com.nettyclient.test;

import io.netty.bootstrap.Bootstrap;
import io.netty.channel.*;
import io.netty.channel.nio.NioEventLoopGroup;
import io.netty.channel.socket.SocketChannel;
import io.netty.channel.socket.nio.NioSocketChannel;

public class Client {

private static final String SERVER_HOST = "127.0.0.1";

public void start(final int beginPort, int nPort) {
System.out.println("client starting....");
EventLoopGroup eventLoopGroup = new NioEventLoopGroup();
final Bootstrap bootstrap = new Bootstrap();
bootstrap.group(eventLoopGroup);
bootstrap.channel(NioSocketChannel.class);
bootstrap.option(ChannelOption.SO_REUSEADDR, true);
bootstrap.handler(new ChannelInitializer<SocketChannel>() {
@Override
protected void initChannel(SocketChannel ch) {
}
});
int index = 0;
int port;
while (!Thread.interrupted()) {
port = beginPort + index;
try {
ChannelFuture channelFuture = bootstrap.connect(SERVER_HOST, port);
channelFuture.addListener((ChannelFutureListener) future -> {
if (!future.isSuccess()) {
System.out.println("连接失败, 退出!");
System.exit(0);
}
});
channelFuture.get();
} catch (Exception e) {
}
if (++index == nPort) {
index = 0;
}
}
}
}

测试

启动服务端

img

启动客户端

img

测试发现当连接数达到13136 的时候,此时达到了最大的连接数,这时候服务器将不再对新的连接进行处理,客户端赢长时间得不到服务端的响应而结束与服务端的连接。(不同的机器配置结果可能不同)
下面通过优化要突破这个连接数。

img

优化

1、局部文件句柄限制

img

一个jvm进程最大能够打开的文件数

修改65535的这个限制
vi /etc/security/limits.conf
在文件末尾添加两行

1
2
*hard nofile 1000000
*soft nofile 1000000

soft和hard为两种限制方式,其中soft表示警告的限制,hard表示真正限制,nofile表示打开的最大文件数。整体表示任何用户一个进程能够打开1000000个文件。注意语句签名有* 号 表示任何用户

img

shutdown -r now 重启linux

再次查看

img

已经修改生效了。

测试

img

最大连接数10万多

2、突破全局文件句柄的限制

cat /proc/sys/fs/file-max
file-max 表示在linux 中最终所有x线程能够打开的最大文件数

img

image.png

修改这个最大值:
sudo vi /etc/sysctl.conf
在文件的末尾添加 fs.file-max=1000000
然后让文件生效 sudo sysctl -p
这个时候再查看一下全局最大文件句柄的数已经变成1000000了

img

测试

img

最大连接数36万多.png

注: 测试的服务器型号

img

cpu 相关配置

img


本文整理自

突破netty单机最大连接数

遵循CC 4.0 BY-SA版权协议


做性能测试的同学,在问到到单台服务器最大连接数时,很多人多会回答是65535,因为最多有65535个端口,一个连接必须要占用一个端口号,所以得出答案是65535,真相到底是什么呢?

在tcp应用中,server事先在某个固定端口监听,client主动发起连接,经过三路握手后建立tcp连接。那么对单机,其最大并发tcp连接数是多少?

如何标识一个TCP连接

在确定最大连接数之前,先来看看系统如何标识一个tcp连接。系统用一个4四元组来唯一标识一个TCP连接:{localip, localport,remoteip,remoteport}。

client最大tcp连接数

client每次发起tcp连接请求时,除非绑定端口,通常会让系统选取一个空闲的本地端口(local port),该端口是独占的,不能和其他tcp连接共享。tcp端口的数据类型是unsigned short,因此本地端口个数最大只有65536,端口0有特殊含义,不能使用,这样可用端口最多只有65535,所以在全部作为client端的情况下,一个client最大tcp连接数为65535,这些连接可以连到不同的serverip。

server最大tcp连接数

server通常固定在某个本地端口上监听,等待client的连接请求。不考虑地址重用(unix的SO_REUSEADDR选项)的情况下,即使server端有多个ip,本地监听端口也是独占的,因此server端tcp连接4元组中只有remoteip(也就是clientip)和remote port(客户端port)是可变的,因此最大tcp连接为客户端ip数×客户端port数,对IPV4,不考虑ip地址分类等因素,最大tcp连接数约为2的32次方(ip数)×2的16次方(port数),也就是server端单机最大tcp连接数约为2的48次方。

实际的tcp连接数

上面给出的是理论上的单机最大连接数,在实际环境中,受到机器资源、操作系统等的限制,特别是sever端,其最大并发tcp连接数远不能达到理论上限。在unix/linux下限制连接数的主要因素是内存和允许的文件描述符个数(每个tcp连接都要占用一定内存,每个socket就是一个文件描述符),另外1024以下的端口通常为保留端口。

对server端,通过增加内存、修改最大文件描述符个数等参数,单机最大并发TCP连接数超过10万,甚至上百万是没问题的


本文整理自

单机最大并发tcp连接数是65535?原来我们都错了!

遵循CC 4.0 BY-SA版权协议


这里不会将UML的各种元素都提到,我只想讲讲类图中各个类之间的关系; 能看懂类图中各个类之间的线条、箭头代表什么意思后,也就足够应对 日常的工作和交流; 同时,我们应该能将类图所表达的含义和最终的代码对应起来; 有了这些知识,看后面章节的设计模式结构图就没有什么问题了;

从一个示例开始

请看以下这个类图,类之间的关系是我们需要关注的:

_images/uml_class_struct.jpg

  • 车的类图结构为<>,表示车是一个抽象类;
  • 它有两个继承类:小汽车和自行车;它们之间的关系为实现关系,使用带空心箭头的虚线表示;
  • 小汽车为与SUV之间也是继承关系,它们之间的关系为泛化关系,使用带空心箭头的实线表示;
  • 小汽车与发动机之间是组合关系,使用带实心箭头的实线表示;
  • 学生与班级之间是聚合关系,使用带空心箭头的实线表示;
  • 学生与身份证之间为关联关系,使用一根实线表示;
  • 学生上学需要用到自行车,与自行车是一种依赖关系,使用带箭头的虚线表示;

下面我们将介绍这六种关系;


类之间的关系

泛化关系(generalization)

类的继承结构表现在UML中为:泛化(generalize)与实现(realize):

继承关系为 is-a的关系;两个对象之间如果可以用 is-a 来表示,就是继承关系:(..是..)

eg:自行车是车、猫是动物

泛化关系用一条带空心箭头的直接表示;如下图表示(A继承自B);

_images/uml_generalization.jpg

eg:汽车在现实中有实现,可用汽车定义具体的对象;汽车与SUV之间为泛化关系;

_images/uml_generalize.jpg

注:最终代码中,泛化关系表现为继承非抽象类;

实现关系(realize)

实现关系用一条带空心箭头的虚线表示;

eg:”车”为一个抽象概念,在现实中并无法直接用来定义对象;只有指明具体的子类(汽车还是自行车),才 可以用来定义对象(”车”这个类在C++中用抽象类表示,在JAVA中有接口这个概念,更容易理解)

_images/uml_realize.jpg

注:最终代码中,实现关系表现为继承抽象类;

聚合关系(aggregation)

聚合关系用一条带空心菱形箭头的直线表示,如下图表示A聚合到B上,或者说B由A组成;

_images/uml_aggregation.jpg

聚合关系用于表示实体对象之间的关系,表示整体由部分构成的语义;例如一个部门由多个员工组成;

与组合关系不同的是,整体和部分不是强依赖的,即使整体不存在了,部分仍然存在;例如, 部门撤销了,人员不会消失,他们依然存在;

组合关系(composition)

组合关系用一条带实心菱形箭头直线表示,如下图表示A组成B,或者B由A组成;

_images/uml_composition.jpg

与聚合关系一样,组合关系同样表示整体由部分构成的语义;比如公司由多个部门组成;

但组合关系是一种强依赖的特殊聚合关系,如果整体不存在了,则部分也不存在了;例如, 公司不存在了,部门也将不存在了;

关联关系(association)

关联关系是用一条直线表示的;它描述不同类的对象之间的结构关系;它是一种静态关系, 通常与运行状态无关,一般由常识等因素决定的;它一般用来定义对象之间静态的、天然的结构; 所以,关联关系是一种“强关联”的关系;

比如,乘车人和车票之间就是一种关联关系;学生和学校就是一种关联关系;

关联关系默认不强调方向,表示对象间相互知道;如果特别强调方向,如下图,表示A知道B,但 B不知道A;

_images/uml_association.jpg

注:在最终代码中,关联对象通常是以成员变量的形式实现的;

依赖关系(dependency)

依赖关系是用一套带箭头的虚线表示的;如下图表示A依赖于B;他描述一个对象在运行期间会用到另一个对象的关系;

_images/uml_dependency.jpg

与关联关系不同的是,它是一种临时性的关系,通常在运行期间产生,并且随着运行时的变化; 依赖关系也可能发生变化;

显然,依赖也有方向,双向依赖是一种非常糟糕的结构,我们总是应该保持单向依赖,杜绝双向依赖的产生;

注:在最终代码中,依赖关系体现为类构造方法及类方法的传入参数,箭头的指向为调用关系;依赖关系除了临时知道对方外,还是“使用”对方的方法和属性;


本文整理自

看懂UML类图和时序图

遵循CC 4.0 BY-SA版权协议


equals和hashCode都是Object对象中的非final方法,它们设计的目的就是被用来覆盖(override)的,所以在程序设计中还是经常需要处理这两个方法的。而掌握这两个方法的覆盖准则以及它们的区别还是很必要的,相关问题也不少。

img

下面我们继续以一次面试的问答,来考察对equals和hashCode的掌握情况。

Java里面有==运算符了,为什么还需要equals


equals()的作用是用来判断两个对象是否相等,在Object里面的定义是:

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

这说明在我们实现自己的equals方法之前,equals等价于==,而==运算符是判断两个对象是不是同一个对象,即他们的地址是否相等。而覆写equals更多的是追求两个对象在逻辑上的相等,你可以说是值相等,也可说是内容相等

在以下几种条件中,不覆写equals就能达到目的:

  • 类的每个实例本质上是唯一的:强调活动实体的而不关心值得,比如Thread,我们在乎的是哪一个线程,这时候用equals就可以比较了。
  • 不关心类是否提供了逻辑相等的测试功能:有的类的使用者不会用到它的比较值得功能,比如Random类,基本没人会去比较两个随机值吧
  • 超类已经覆盖了equals,子类也只需要用到超类的行为:比如AbstractMap里已经覆写了equals,那么继承的子类行为上也就需要这个功能,那也不需要再实现了。
  • 类是私有的或者包级私有的,那也用不到equals方法:这时候需要覆写equals方法来禁用它:@Override public boolean equals(Object obj) { throw new AssertionError();}

覆写equals时有哪些准则?


这个我在Effective Java上看过,没记错的话应该是:

自反性:对于任何非空引用值 x,x.equals(x) 都应返回 true。

对称性:对于任何非空引用值 x 和 y,当且仅当 y.equals(x) 返回 true 时,x.equals(y) 才应返回 true。

传递性:对于任何非空引用值 x、y 和 z,如果 x.equals(y) 返回 true, 并且 y.equals(z) 返回 true,那么 x.equals(z) 应返回 true。

一致性:对于任何非空引用值 x 和 y,多次调用 x.equals(y) 始终返回 true 或始终返回 false, 前提是对象上 equals 比较中所用的信息没有被修改。

非空性:对于任何非空引用值 x,x.equals(null) 都应返回 false。

哪些情况下会违反对称性和传递性


违反对称性

对称性就是x.equals(y)时,y也得equals x,很多时候,我们自己覆写equals时,让自己的类可以兼容等于一个已知类,比如下面的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public final class CaseInsensitiveString {
private final String s;
public CaseInsensitiveString(String s) {
if (s == null)
throw new NullPointerException();
this.s = s;
}

@Override
public boolean equals(Object o) {
if (o instanceof CaseInsensiticeString)
return s.equalsIgnoreCase(((CaseInsensitiveString)o).s);
if (o instanceof String)
return s.equalsIgnoreCase((String) o);
return false;
}
}

这个想法很好,想创建一个无视大小写的String,并且还能够兼容String作为参数,假设我们创建一个CaseInsensitiveString:

1
CaseInsensitiveString cis = new CaseInsensitiveString("Case");

那么肯定有cis.equals("case"),问题来了,"case".equals(cis)吗?String并没有兼容CaseInsensiticeString,所以String的equals也不接受CaseInsensiticeString作为参数。

所以有个准则,一般在覆写equals只兼容同类型的变量

违反传递性

传递性就是A等于B,B等于C,那么A也应该等于C。

假设我们定义一个类Cat。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Cat()
{
private int height;
private int weight;
public Cat(int h, int w)
{
this.height = h;
this.weight = w;
}

@Override
public boolean equals(Object o) {
if (!(o instanceof Cat))
return false;
Cat c = (Cat) o;
return c.height == height && c.weight == weight;
}
}

名人有言,不管黑猫白猫抓住老鼠就是好猫,我们又定义一个类ColorCat:

1
2
3
4
5
6
7
8
public class ColorCat extends()
{
private String color;
public ColorCat(int h, int w, String color)
{
super(h, w);
this.color = color;
}

我们在实现equals方法时,可以加上颜色比较,但是加上颜色就不兼容和普通猫作对比了,这里我们忘记上面要求只兼容同类型变量的建议,定义一个兼容普通猫的equals方法,在“混合比较”时忽略颜色。

1
2
3
4
5
6
7
8
@Override
public boolean equals(Object o) {
if (! (o instanceof Cat))
return false; //不是Cat或者ColorCat,直接false
if (! (o instanceof ColorCat))
return o.equals(this);//不是彩猫,那一定是普通猫,忽略颜色对比
return super.equals(o)&&((ColorCat)o).color.equals(color); //这时候才比较颜色
}

假设我们定义了猫:

1
2
3
ColorCat whiteCat = new ColorCat(1,2,"white");
Cat cat = new Cat(1,2);
ColorCat blackCat = new ColorCat(1,2,"black");

此时有whiteCat等于cat,cat等于blackCat,但是whiteCat不等于blackCat,所以不满足传递性要求。

所以在覆写equals时,一定要遵守上述的5大军规,不然总是有麻烦事找上门来。

有覆写equals方法的诀窍吗,比如写一下String里面的equals?


手写:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if (anObject instanceof String) {
String anotherString = (String)anObject;
int n = value.length;
if (n == anotherString.value.length) {
char v1[] = value;
char v2[] = anotherString.value;
int i = 0;
while (n-- != 0) {
if (v1[i] != v2[i])
return false;
i++;
}
return true;
}
}
return false;
}

上面的equals有以下几点诀窍:

  • 使用==操作符检查“参数是否为这个对象的引用”:如果是对象本身,则直接返回,拦截了对本身调用的情况,算是一种性能优化。
  • 使用instanceof操作符检查“参数是否是正确的类型”:如果不是,就返回false,正如对称性和传递性举例子中说得,不要想着兼容别的类型,很容易出错。在实践中检查的类型多半是equals所在类的类型,或者是该类实现的接口的类型,比如Set、List、Map这些集合接口。
  • 把参数转化为正确的类型: 经历了上一步的检测,基本会成功。
  • 对于该类中的“关键域”,检查参数中的域是否与对象中的对应域相等:基本类型的域就用==比较,float域用Float.compare方法,double域用Double.compare方法,至于别的引用域,我们一般递归调用它们的equals方法比较,加上判空检查和对自身引用的检查,一般会写成这样:(field == o.field || (field != null && field.equals(o.field))),而上面的String里使用的是数组,所以只要把数组中的每一位拿出来比较就可以了。
  • 编写完成后思考是否满足上面提到的对称性,传递性,一致性等等

还有一些注意点。

覆盖equals时一定要覆盖hashCode

equals函数里面一定要是Object类型作为参数

equals方法本身不要过于智能,只要判断一些值相等即可。

hashCode什么用


hashCode用于返回对象的hash值,主要用于查找的快捷性,因为hashCode也是在Object对象中就有的,所以所有Java对象都有hashCode,在HashTable和HashMap这一类的散列结构中,都是通过hashCode来查找在散列表中的位置的。

如果两个对象equals,那么它们的hashCode必然相等,

但是hashCode相等,equals不一定相等。(有哈希碰撞)

以HashMap为例,使用的是链地址法来处理散列,假设有一个长度为8的散列表

1
0 1 2 3 4 5 6 7

那么,当往里面插数据时,是以hashCode作为key插入的,一般hashCode%8得到所在的索引,如果所在索引处有元素了,则使用一个链表,把多的元素不断链接到该位置,这边也就是大概提一下HashMap原理。所以hashCode的作用就是找到索引的位置,然后再用equals去比较元素是不是相等,形象一点就是先找到桶(bucket),然后再在里面找东西。

hashCode 的常规协定是:
在 Java 应用程序执行期间,在同一对象上多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是对象上 equals 比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行,该整数无需保持一致。

以下情况不 是必需的:如果根据 equals(java.lang.Object) 方法,两个对象不相等,那么在两个对象中的任一对象上调用 hashCode 方法必定会生成不同的整数结果。但是,程序员应该知道,为不相等的对象生成不同整数结果可以提高哈希表的性能。

实际上,由 Object 类定义的 hashCode 方法确实会针对不同的对象返回不同的整数。(这一般是通过将该对象的内部地址转换成一个整数来实现的,但是 JavaTM 编程语言不需要这种实现技巧。)

当equals方法被重写时,通常有必要重写 hashCode 方法,以维护 hashCode 方法的常规协定,该协定声明相等对象必须具有相等的哈希码。

具体的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
Stu s1 = new Stu("张三", 18);
Stu s2 = new Stu("张三", 18);
System.out.println("stu:" + s1.equals(s2));

Set<Stu> set = new HashSet<>();
set.add(s1);
System.out.println("s1 hashCode:" + s1.hashCode());
System.out.println("add s1 size:" + set.size());
set.add(s2);
System.out.println("s2 hashCode:" + s2.hashCode());
System.out.println("add s2 size::" + set.size());
}

输出结果:

1
2
3
4
5
stu:false
s1 hashCode:1317241155
add s1 size:1
s2 hashCode:463175162
add s2 size::2

Java中的Set是不允许有重复元素的,所以这里set的size由1变成了2,因为两个Stu都是new出来的,分配的地址不一样,那么Set是通过equals来定义重复的吗?

首先重写Stu的equals方法:

1
2
3
4
5
6
7
8
9
10
@Override
public boolean equals(Object obj) {
if (obj == null){
return false;
}
if (obj.getClass() != getClass()){
return false;
}
return ((Stu)obj).getName().equals(getName());
}

输出结果:

1
2
3
4
5
stu:true
s1 hashCode:713679046
add s1 size:1
s2 hashCode:1107557627
add s2 size::2

重写equals方法,name相同就让equals返回true了,但是Set的size还是发生了改变,就说明不是有equals方法来定义重复的,现在仅仅重写hashCode方法:

1
2
3
4
@Override
public int hashCode() {
return getName().hashCode();
}

输出结果:

1
2
3
4
5
stu:false
s1 hashCode:774889
add s1 size:1
s2 hashCode:774889
add s2 size::2

仅重写了hashCode方法,所以equals返回false,然后hashCode由name属性的hashCode方法得到,所以hashCode相等,但是Set的size还是改变了,这说明Set也不是仅仅依据hashCode来定义重复。

那么现在将上述equals和hashCode两者同时重写,输出结果:

1
2
3
4
5
stu:true
s1 hashCode:774889
add s1 size:1
s2 hashCode:774889
add s2 size::1

结合上面引用的案例,可以类推,hash类存储结构(HashSet、HashMap等等)添加元素会有重复性校验,校验的方式就是先取hashCode判断是否相等(找到对应的位置,该位置可能存在多个元素),然后再取equals方法比较(极大缩小比较范围,高效判断),最终判定该存储结构中是否有重复元素。

有哪些覆写hashCode的诀窍?


一个好的hashCode的方法的目标:为不相等的对象产生不相等的散列码,同样的,相等的对象必须拥有相等的散列码。

好的散列函数要把实例均匀的分布到所有散列值上,结合前人的经验可以采取以下方法:

引自Effective Java

  1. 把某个非零的常数值,比如17,保存在一个int型的result中;

  2. 对于每个关键域f(equals方法中设计到的每个域),作以下操作:

    a. 为该域计算int类型的散列码;

    1
    2
    3
    4
    5
    6
    7
    i.如果该域是boolean类型,则计算(f?1:0),
    ii.如果该域是byte,char,short或者int类型,计算(int)f,
    iii.如果是long类型,计算(int)(f^(f>>>32)).
    iv.如果是float类型,计算Float.floatToIntBits(f).
    v.如果是double类型,计算Double.doubleToLongBits(f),然后再计算long型的hash值
    vi.如果是对象引用,则递归的调用域的hashCode,如果是更复杂的比较,则需要为这个域计算一个范式,然后针对范式调用hashCode,如果为null,返回0
    vii. 如果是一个数组,则把每一个元素当成一个单独的域来处理。

    b.result = 31 * result + c;

  3. 返回result

  4. 编写单元测试验证有没有实现所有相等的实例都有相等的散列码。

这里再说下2.b中为什么采用31*result + c,乘法使hash值依赖于域的顺序,如果没有乘法那么所有顺序不同的字符串String对象都会有一样的hash值,而31是一个奇素数,如果是偶数,并且乘法溢出的话,信息会丢失,31有个很好的特性是31*i ==(i<<5)-i,即2的5次方减1,虚拟机会优化乘法操作为移位操作的。

给个简单的例子:

1
2
3
4
5
6
@Override
public int hashCode() {
int result = 17;
result = 31 * result + getName().hashCode();
return result;
}

本文整理自

面试官爱问的equals与hashCode

equals和hashCode的区别和联系

遵循CC 4.0 BY-SA版权协议