[Java核心技术] Java数据结构

2022-02-17 约 10557 字预计阅读 22 分钟次阅读

Java 核心技术读书笔记——Java数据结构

1 数组

数组是一个存放多个数据的容器
- 数据是同一种类型
- 所有的数据是线性规则排列
- 可通过位置索引来快速定位访问数据
- 需明确容器长度

1.1 定义和初始化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20



public class ArrayTest {

  public static void main(String[] args) {
    
    int a[]; //a 还没有new操作  实际上是null，也不知道内存位置
    int[] b; //b 还没有new操作  实际上是null，也不知道内存位置
    int[] c = new int[2]; //c有2个元素，都是0
    c[0] = 10; c[1] = 20; //逐个初始化
    
    int d[] = new int[]{0,2,4};//d有3个元素, 0,2,4，同时定义和初始化
    int d1[] = {1,3,5};        //d1有3个元素, 1,3,5 同时定义和初始化
    
    //注意声明变量时候没有分配内存，不需要指定大小，以下是错误示例
    //int e[5];
    //int[5] f;
    //int[5] g = new int[5];
    //int h[5] = new int[5];
  }
}

1.2 数组索引

数组的length属性标识数组的长度
从0开始，到length-1
数组不能越界访问，否则会报ArrayIndexOutBoundsException异常

1.3 数组遍历

需要自己控制索引位置

1
2
3
4


//需要自己控制索引位置
for(int i=0;i<d.length;i++) {
  System.out.println(d[i]);
}

无需控制索引位置

1
2
3
4


//无需控制索引位置
for(int e : d) {
  System.out.println(e);
}

1.4 多维数组

数组的数组
存储是按照行存储原则
规则数组

1

int a[][] = new int[2][3];

不规则数组

1
2
3
4
5


int b[][];
    b = new int[3][];
    b[0]=new int[3];
    b[1]=new int[4];
    b[2]=new int[5];

遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


int k = 0;
for(int i=0;i<a.length;i++)
{
  for(int j=0;j<a[i].length;j++)
  {
    a[i][j] = ++k; 
  }
}

for(int[] items : a)
{
  for(int item : items)
  {
    System.out.print(item + ", ");
  }
  System.out.println();
}

2 JCF(Java Collection Framework)

容器：能够存放数据的空间结构
- 数组/多维数组，只能线性存放
- 列表/散列集/树/……
容器框架：为表示和操作容器而规定的一种标准体系结构
- 对外的接口：容器中所能存放的抽象数据类型
- 接口的实现：可复用的数据结构
- 算法：对数据的查找和排序
容器框架的优点：提高数据存取效率，避免程序员重复劳动
JCF的集合接口是Collection
- add 增加；
- contains 包含；
- remove 删除；
- size 数据元素个数；
- iterator 迭代器；
JCF的迭代器接口Iterator
- hasNext 判断是否有下一个元素；
- next 获取下一个元素；
- remove 删除某一个元素；
JCF主要的数据结构实现类
- 列表（List，ArrayList，LinkedList）
- 集合（Set，HashSet，TreeSet，LinkedHashSet）
- 映射（Map，HashMap，TreeMap，LinkedHashMap）
JCF主要的算法类
- Arrays：对数组进行查找和排序等操作
- Collections：对Collection及其子类进行排序和查找操作

3 `List`

List：列表
- 有序的Collection
- 允许重复元素
- {1,2,4,{5,2},1,3}
List主要实现
- ArrayList（非同步的）
- LinkedList（非同步）
- Vector（同步）

3.1 `ArrayList`

以数组实现的列表，不支持同步
利用索引位置可以快速定位访问
不适合指定位置的插入、删除操作
适合变动不大，主要用于查询的数据
和Java数组相比，其容量是可动态调整的
ArrayList在元素填满容器时会自动扩充容器大小的50%
ArrayList只能装对象，当add(3)时，会自动将普通int变量3自动装箱为Integer(3)的对象，然后放入ArrayList容器中。

声明和初始化

1
2


import java.util.ArrayList;
ArrayList<Integer> al = new ArrayList<Integer>(); 

`add`

1
2
3


al.add(3);
al.add(new Integer(6));  
al.add(2, 9);  //将9插入到第4个元素，后面元素往后挪动

`remove`

1

al.remove(3);  //删除第四个元素，后面元素往前挪动

遍历

 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


import java.util.ArrayList;
import java.util.Iterator;

public static void traverseByIterator(ArrayList<Integer> al)
{
    System.out.println("============迭代器遍历==============");  //慢
    Iterator<Integer> iter1 = al.iterator();  
    while(iter1.hasNext()){  
        System.out.println(iter1.next());  
    }
}
public static void traverseByIndex(ArrayList<Integer> al)
{
    System.out.println("============随机索引值遍历=============="); //中
    for(int i=0;i<al.size();i++)
    {
      System.out.println(al.get(i));
    }
}
public static void traverseByFor(ArrayList<Integer> al)
{
    System.out.println("============for循环遍历=============="); //快
    for(Integer item : al)
    {
      System.out.println(item);
    }
}

3.2 `LinkedList`

以双向链表实现的列表，不支持同步
可被当作堆栈、队列、和双端队列进行操作
顺序访问高效，随机访问较差，中间插入和删除高效
适用于经常变化的数据

声明和初始化

1
2


import java.util.LinkedList;
LinkedList<Integer> ll = new LinkedList<Integer>();  

`add`

1
2
3
4
5
6
7


ll.add(3);  
ll.add(2);  
ll.add(5);  
ll.add(6);  
ll.add(6);  
ll.addFirst(9);  //在头部增加9
ll.add(3, 10);   //将10插入到第四个元素，四以及后续的元素往后挪动

`remove`

1

ll.remove(3);    //将第四个元素删除

遍历

 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


import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

  public static void traverseByIterator(LinkedList<Integer> list)
  {
    System.out.println("============迭代器遍历==============");  //中
    Iterator<Integer> iter1 = list.iterator();  
    while(iter1.hasNext()){  
      System.out.println(iter1.next());  
    }
  }
  public static void traverseByIndex(LinkedList<Integer> list)
  {
    System.out.println("============随机索引值遍历=============="); //慢
    for(int i=0;i<list.size();i++)
    {
      System.out.println(list.get(i));
    }
  }
  public static void traverseByFor(LinkedList<Integer> list)
  {
    System.out.println("============for循环遍历=============="); //快
    for(Integer item : list)
    {
      System.out.println(item);
    }
  }

`ArrayList`与`LinkedList`对比

 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
94
95
96


import java.util.ArrayList;
import java.util.LinkedList;

public class ListCompareTest {

  public static void main(String[] args) {
    int times = 10 * 1000;
      // times = 100 * 1000;
      // times = 1000 * 1000;
      
    ArrayList<Integer> arrayList = new ArrayList<Integer>();
      LinkedList<Integer> linkedList = new LinkedList<Integer>();

      System.out.println("Test times = " + times);
      System.out.println("-------------------------");
      
      // ArrayList add
      long startTime = System.nanoTime();

      for (int i = 0; i < times; i++) {
          arrayList.add(0,i);
      }
      long endTime = System.nanoTime();
      long duration = endTime - startTime;
      System.out.println(duration + " <--ArrayList add");

      // LinkedList add
      startTime = System.nanoTime();

      for (int i = 0; i < times; i++) {
          linkedList.add(0,i);
      }
      endTime = System.nanoTime();
      duration = endTime - startTime;
      System.out.println(duration + " <--LinkedList add");
      System.out.println("-------------------------");
      
      // ArrayList get
      startTime = System.nanoTime();

      for (int i = 0; i < times; i++) {
          arrayList.get(i);
      }
      endTime = System.nanoTime();
      duration = endTime - startTime;
      System.out.println(duration + " <--ArrayList get");

      // LinkedList get
      startTime = System.nanoTime();

      for (int i = 0; i < times; i++) {
          linkedList.get(i);
      }
      endTime = System.nanoTime();
      duration = endTime - startTime;
      System.out.println(duration + " <--LinkedList get");
      System.out.println("-------------------------");

      // ArrayList remove
      startTime = System.nanoTime();

      for (int i = 0; i < times; i++) {
          arrayList.remove(0);
      }
      endTime = System.nanoTime();
      duration = endTime - startTime;
      System.out.println(duration + " <--ArrayList remove");

      // LinkedList remove
      startTime = System.nanoTime();

      for (int i = 0; i < times; i++) {
          linkedList.remove(0);
      }
      endTime = System.nanoTime();
      duration = endTime - startTime;
      System.out.println(duration + " <--LinkedList remove");
  }
}

/**
 * 
 * 输出结果
 * Test times = 10000
 * -------------------------
 * 3857300 <--ArrayList add
 * 848700 <--LinkedList add
 * -------------------------
 * 363100 <--ArrayList get
 * 32779501 <--LinkedList get
 * -------------------------
 * 3671900 <--ArrayList remove
 * 495300 <--LinkedList remove
 * 
 * 
 */

由以上代码可知
- LinkedList 使用于频繁增删的数据
- ArrayList适用于查询的（静态）数据

3.3 `Vector`

和ArrayList一样，可变数组实现的列表
Vector同步，适合在多线程下使用
官方文档建议，在非同步情况下，优先采用ArrayList

声明和初始化

1
2


import java.util.Vector;
Vector<Integer> v = new Vector<Integer>();

`add`

1
2
3
4


v.add(1);
v.add(2);
v.add(3);
v.add(1, 5);

`remove`

1

v.remove(2);

遍历

 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


import java.util.Iterator;
import java.util.Vector;

public static void traverseByIterator(Vector<Integer> v) {
  System.out.println("============迭代器遍历=============="); //最慢
  Iterator<Integer> iter1 = v.iterator();
  while (iter1.hasNext()) {
    System.out.println(iter1.next());
  }
}

public static void traverseByIndex(Vector<Integer> v) {
  System.out.println("============随机索引值遍历=============="); //较快
  for (int i = 0; i < v.size(); i++) {
    System.out.println(v.get(i));
  }
}

public static void traverseByFor(Vector<Integer> v) {
  System.out.println("============for循环遍历=============="); //最快
  for (Integer item : v) {
    System.out.println(item);
  }
}

public static void traverseByEnumeration(Vector<Integer> v) {
  System.out.println("============Enumeration遍历==============");//较慢
  for (Enumeration<Integer> enu = v.elements(); enu.hasMoreElements();) {
    enu.nextElement();
  }
}

4 集合`Set`

确定性：对任意对象都能判定其是否属于某一个集合
互异性：集合内每个元素都是不相同的，注意是内同互异
无序性：集合内的顺序无关

4.1 `Java`中的集合接口`Set`

HashSet：基于散列函数的集合，无序，不支持同步
TreeSet：基于树结构的集合，可排序的，不支持同步
LinkedHashSet：基于散列函数和双向链表的集合，可排序的，不支持同步

4.2 `HashSet`

基于HashMap实现的，可以容纳null元素，不支持同步
- 将不同步的HashSet变为同步的HashSet
  1
  
  Set s = Collections.synchronizedSet(new HashSet(...));

声明和初始化

1
2


import java.util.HashSet;
HashSet<Integer> hs = new HashSet<Integer>();

`add` 添加一个元素

1
2
3
4
5
6
7
8


hs.add(null);
hs.add(1000);
hs.add(20);
hs.add(3);
hs.add(40000);
hs.add(5000000);
hs.add(3);                      //3 重复
hs.add(null);   

`clear` 清除整个`HashSet`

1

hs.clear();

`contains` 判定是否包含一个元素

1
2
3
4


if(!hs.contains(6))
{
  hs.add(6);
}

`remove` 删除一个元素

1

hs.remove(4);

`size` 大小

1

hs.size();

`retainAll` 计算两个集合交集

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


System.out.println("============测试集合交集==============");
      
HashSet<String> set1 = new HashSet<String>();
HashSet<String> set2 = new HashSet<String>();

set1.add("a");
set1.add("b");
set1.add("c");

set2.add("c");
set2.add("d");
set2.add("e");

//交集
set1.retainAll(set2);
System.out.println("交集是 "+set1);

遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
 
public static void traverseByIterator(HashSet<Integer> hs)
{
  System.out.println("============迭代器遍历=============="); 
  Iterator<Integer> iter1 = hs.iterator();  
  while(iter1.hasNext()){  
      System.out.println(iter1.next());  
  }
}
public static void traverseByFor(HashSet<Integer> hs)
{
  System.out.println("============for循环遍历=============="); 
  for(Integer item : hs)
  {
    System.out.println(item);
  }
}

4.3 `TreeSet`

基于TreeMap实现，不可以容纳null元素，不支持同步

将不同步的TreeSet变为同步的TreeSet

1

SortedSet s = Collections.synchronizedSortrfSet(new TreeSet(...));

根据CompareTo方法或指定Comparator排序

声明和初始化

1
2


import java.util.TreeSet;
TreeSet<Integer> ts = new TreeSet<Integer>();

`add` 添加一个元素

1
2
3
4
5
6
7


// ts.add(null);  错误，不支持null
ts.add(1000);
ts.add(20);
ts.add(3);
ts.add(40000);
ts.add(5000000);
ts.add(3);                      //3 重复  

`clear` 清除整个`TreeSet`

1

ts.clear();

`contains` 判定是否包含一个元素

1
2
3
4


if(!ts.contains(6))
{
  ts.add(6);
}

`remove` 删除一个元素

1

ts.remove(4);

`size` 大小

1

ts.size();

遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


import java.util.Iterator;
import java.util.TreeSet;

public static void traverseByIterator(TreeSet<Integer> hs)
{
  System.out.println("============迭代器遍历=============="); 
  Iterator<Integer> iter1 = hs.iterator();  
  while(iter1.hasNext()){  
      System.out.println(iter1.next());  
  }
}
public static void traverseByFor(TreeSet<Integer> hs)
{
  System.out.println("============for循环遍历=============="); 
  for(Integer item : hs)
  {
    System.out.println(item);
  }
}

4.4 `LinkedHashSet`

基于HashMap实现的，可以容纳null元素，不支持同步
- 将不同步的LinkedHashSet变为同步的LinkedHashSet
  1
  
  Set s = Collections.synchronizedSet(new LinkedHashSet(...));
方法和HashSet基本一致
通过一个双向链表维护插入顺序

声明和初始化

1
2


import java.util.LinkedHashSet;
LinkedHashSet<Integer> lhs = new LinkedHashSet<Integer>();

`add`

1
2
3
4
5
6
7
8


lhs.add(null);
lhs.add(1000);
lhs.add(20);
lhs.add(3);
lhs.add(40000);
lhs.add(5000000);
lhs.add(3);                      //3 重复
lhs.add(null);                   //null 重复

`remove`

1

lhs.remove(4);

`clear`

1

lhs.clear();

`contains`

1
2
3
4


if(!lhs.contains(6))
{
  lhs.add(6);
}

`size`

1

lhs.size();

遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


import java.util.Iterator;
import java.util.LinkedHashSet;
public static void traverseByIterator(LinkedHashSet<Integer> hs)
{
  System.out.println("============迭代器遍历=============="); 
  Iterator<Integer> iter1 = hs.iterator();  
  while(iter1.hasNext()){  
      System.out.println(iter1.next());  
  }
}
public static void traverseByFor(LinkedHashSet<Integer> hs)
{
  System.out.println("============for循环遍历=============="); 
  for(Integer item : hs)
  {
    System.out.println(item);
  }
}

4.5 异同点

HashSet，LinkedHashSet，TreeSet的元素都只能是对象

HashSet和LinkedHashSet判定元素重复的原则

判定两个元素的hashCode返回值是否相同，若不同，返回false
若两者hashCode相同，判定equals方法，若不同，返回false；否则返回true
hashCode和equals方法是所有类都有的，因为Object类有

  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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171


// Cat.java
class Cat
{
  private int size;

  public Cat(int size)
  {
    this.size = size;
  }
}

// Dog.java
class Dog {
    private int size;

    public Dog(int s) {
        size = s;
    }      
    public int getSize() {
    return size;
  }
  /**
   * 
   * 这三个方法三位一体，
   * equals()是相同的；
   * hashCode()是相同的；
   * toString()也应该相同；
   * 
   */
  public boolean equals(Object obj2)   {
      System.out.println("Dog equals()~~~~~~~~~~~");
      if(0==size - ((Dog) obj2).getSize()) {
        return true;
      } else {
        return false;
      }
    }

    public int hashCode() {
      System.out.println("Dog hashCode()~~~~~~~~~~~");
      return size;
    }

    public String toString() {
      System.out.print("Dog toString()~~~~~~~~~~~");
        return size + "";
    }
}

//Tiger.java
public class Tiger implements Comparable{
  private int size;

    public Tiger(int s) {
        size = s;    
    }    

    public int getSize() {
    return size;
  }

  public int compareTo(Object o) {
      System.out.println("Tiger compareTo()~~~~~~~~~~~");
        return size - ((Tiger) o).getSize();
    }
}

// ObjectHashSetTest.java
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.TreeSet;


public class ObjectHashSetTest {

  public static void main(String[] args) {
    /**
     * 
     * Cat类本身没有hashCode(),而是继承Object类的，
     * 而Object类的hashCode()会返回对象信息和内存地址经过运算的一个int值
     * 两个Cat(4)对象，它们的hashCode()返回值是不同的。
     * 
     */
    System.out.println("==========Cat HashSet ==============");
    HashSet<Cat> hs = new HashSet<Cat>();  
    hs.add(new Cat(2));  
    hs.add(new Cat(1));  
    hs.add(new Cat(3));  
    hs.add(new Cat(5));  
    hs.add(new Cat(4)); 
    hs.add(new Cat(4)); 
    System.out.println(hs.size());  //6

    System.out.println("========================");
    LinkedHashSet<Cat> lhs= new LinkedHashSet<Cat>();  
    lhs.add(new Cat(2));  
    lhs.add(new Cat(1));  
    lhs.add(new Cat(3));  
    lhs.add(new Cat(5));  
    lhs.add(new Cat(4));  
    lhs.add(new Cat(4));    
    System.out.println(lhs.size());  //6

    /**
     * 
     * Dog类本身改写了hashCode()方法，子返回值是具体的size。
     * 所以两个不同Dog(4)，它们的hashCode()返回值是相同的。
     * 
     */
    System.out.println("==========Dog HashSet ==============");
    HashSet<Dog> hs2 = new HashSet<Dog>();  
    hs2.add(new Dog(2));  
    hs2.add(new Dog(1));  
    hs2.add(new Dog(3));  
    hs2.add(new Dog(5));  
    hs2.add(new Dog(4)); 
    hs2.add(new Dog(4)); 
    System.out.println(hs2.size());  //5

    System.out.println("========================");
    LinkedHashSet<Dog> lhs2= new LinkedHashSet<Dog>();  
    lhs2.add(new Dog(2));  
    lhs2.add(new Dog(1));  
    lhs2.add(new Dog(3));  
    lhs2.add(new Dog(5));  
    lhs2.add(new Dog(4));  
    lhs2.add(new Dog(4));     
    System.out.println(lhs2.size());  //5

    /**
     * 
     * Java四个重要接口：
     * Comparable：可比较的；
     * Clonable：可克隆的；
     * Runnable：可线程化的；
     * Serializable：可序列化的；
     * 
     * Tiger实现Comparable接口，所以必须实现compareTo方法比较大小
     * compareTo方法具体规则如下：
     * int a = obj1.comparaTo(obj2);
     * 如果 a >  0，则obj1 > obj2；
     * 如果 a == 0，则obj1 == obj2；
     * 如果 a <  0，则obj1 < obj2；
     * 
     * 
     * HashSet元素判定规则和comparaTo方法无关
     * 
     */
    System.out.println("==========Tiger HashSet ==============");   
    HashSet<Tiger> hs3 = new HashSet<Tiger>();  
    hs3.add(new Tiger(2));  
    hs3.add(new Tiger(1));  
    hs3.add(new Tiger(3));  
    hs3.add(new Tiger(5));  
    hs3.add(new Tiger(4)); 
    hs3.add(new Tiger(4)); 
    System.out.println(hs3.size());  //6

    System.out.println("========================");
    LinkedHashSet<Tiger> lhs3= new LinkedHashSet<Tiger>();  
    lhs3.add(new Tiger(2));  
    lhs3.add(new Tiger(1));  
    lhs3.add(new Tiger(3));  
    lhs3.add(new Tiger(5));  
    lhs3.add(new Tiger(4));  
    lhs3.add(new Tiger(4));     
    System.out.println(lhs3.size());  //6
  }
}

TreeSet判定元素重复的原则

需要元素继承自Comparable接口
比较两个元素的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


//Tiger.java
public class Tiger implements Comparable{
  private int size;

    public Tiger(int s) {
        size = s;    
    }    

    public int getSize() {
    return size;
  }

  public int compareTo(Object o) {
      System.out.println("Tiger compareTo()~~~~~~~~~~~");
        return size - ((Tiger) o).getSize();
    }
}

// ObjectTreeSetTest.java
import java.util.TreeSet;

public class ObjectTreeSetTest {

  public static void main(String[] args) {
    //添加到TreeSet的，需要实现Comparable接口，即实现compareTo方法

    System.out.println("==========Tiger TreeSet ==============");


    TreeSet<Tiger> ts3 = new TreeSet<Tiger>();  
    ts3.add(new Tiger(2));  
    ts3.add(new Tiger(1));  
    ts3.add(new Tiger(3));  
    ts3.add(new Tiger(5));  
    ts3.add(new Tiger(4)); 
    ts3.add(new Tiger(4)); 
    System.out.println(ts3.size());  //5
  }
}

5 映射`Map`

Map映射
- 数学定义：两个集合之间的元素对应关系
- 一个输入对应到一个输出
- {Key,Value}，键值对，K-V对
Java中Map
- Hashtable（同步，慢，数据量小）
- HashMap（不支持同步，快，数据量大）
- Properties（同步，文件形式，数据量小）

5.1 `Hashtable`

K-V对，K和V都不允许为null
同步，多线程安全
无序的
适合小数据量

定义和初始化

1
2


import java.util.Hashtable;
Hashtable<Integer,String> ht =new  Hashtable<Integer,String>();

`clear`

清空数据

1

ht.clear();

`contains/containsValue`

是否包含某一个值

1
2


ht.contains("aaa");
ht.containsValue("aaa");

`containsKey`

是否包含某一个Key

1

ht.containsKey(30000);

`get`

根据Key获取相应的值

1

ht.get(30000);

`put`

增加新的K-V对

1
2
3
4
5
6
7


//ht.put(1, null); 编译不报错  运行报错
//ht.put(null,1);  编译报错
ht.put(1000, "aaa");
ht.put(2, "bbb");
ht.put(30000, "ccc");

ht.put(30000, "ddd");  //更新覆盖ccc

`remove`

删除某一个K-V对

1

ht.remove(2);

`size`

返回数据大小

1

ht.size();

遍历

 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


public static void traverseByEntry(Hashtable<Integer,String> ht)
{
  System.out.println("============Entry迭代器遍历==============");
  Integer key;
  String value;
  Iterator<Entry<Integer, String>> iter = ht.entrySet().iterator();
  while(iter.hasNext()) {
      Map.Entry<Integer, String> entry = iter.next();
      // 获取key
      key = entry.getKey();
      // 获取value
      value = entry.getValue();
      //System.out.println("Key:" + key + ", Value:" + value);
  }
}
  
  
public static void traverseByKeySet(Hashtable<Integer,String> ht)
{
  System.out.println("============KeySet迭代器遍历=============="); 
  Integer key;
  String value;
  Iterator<Integer> iter = ht.keySet().iterator();
  while(iter.hasNext()) {
      key = iter.next();        
      // 获取value
      value = ht.get(key);
      //System.out.println("Key:" + key + ", Value:" + value);
  }
}


public static void traverseByKeyEnumeration(Hashtable<Integer,String> ht)
{
  System.out.println("============KeyEnumeration迭代器遍历=============="); 
  Integer key;
  String value;
  Enumeration<Integer> keys = ht.keys();
  while(keys.hasMoreElements()) {
      key = keys.nextElement();   
      // 获取value
      value = ht.get(key);
      //System.out.println("Key:" + key + ", Value:" + value);
  }
}

5.2 `HashMap`

K-V对，K和V都允许为null
无序的
不同步，多线程不安全
- 将不同步的HashMap变为同步的HashMap
  1
  
  Map m = Collections.synchronizedMap(new HashMap(...));

定义和初始化

1
2


import java.util.HashMap;
HashMap<Integer,String> hm =new  HashMap<Integer,String>();

`clear`

清空数据

1

hm.clear();

`containsValue`

是否包含某一个值

1

hm.containsValue("aaa")

`containsKey`

是否包含某一个Key

1

hm.containsKey(30000)

`get`

根据Key获取相应的值

1

hm.get(30000)

`put`

增加新的K-V对

1
2
3
4
5
6
7


hm.put(1, null); 
hm.put(null, "abc");  
hm.put(1000, "aaa");
hm.put(2, "bbb");
hm.put(30000, "ccc");

hm.put(30000, "ddd");  //更新覆盖ccc

`remove`

删除某一个K-V对

1

hm.remove(2);

`size`

返回数据大小

1

hm.size()

遍历

 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


public static void traverseByEntry(HashMap<Integer,String> hm)
{
  System.out.println("============Entry迭代器遍历==============");
  Integer key;
  String value;
  Iterator<Entry<Integer, String>> iter = hm.entrySet().iterator();
  while(iter.hasNext()) {
      Map.Entry<Integer, String> entry = iter.next();
      // 获取key
      key = entry.getKey();
      // 获取value
      value = entry.getValue();
      //System.out.println("Key:" + key + ", Value:" + value);
  }
}


public static void traverseByKeySet(HashMap<Integer,String> hm)
{
  System.out.println("============KeySet迭代器遍历=============="); 
  Integer key;
  String value;
  Iterator<Integer> iter = hm.keySet().iterator();
  while(iter.hasNext()) {
      key = iter.next();        
      // 获取value
      value = hm.get(key);
      //System.out.println("Key:" + key + ", Value:" + value);
  }
}

5.3 `LinkedHashMap`

基于双向链表的维持插入顺序的HashMap
遍历顺序和它的插入顺序保持一致

定义和初始化

1
2


import java.util.LinkedHashMap;
LinkedHashMap<Integer,String> lhm =new  LinkedHashMap<Integer,String>();

`clear`

清空数据

1

lhm.clear();

`containsValue`

是否包含某一个值

1

lhm.containsValue("aaa")

`containsKey`

是否包含某一个Key

1

lhm.containsKey(30000)

`get`

根据Key获取相应的值

1

lhm.get(30000)

`put`

增加新的K-V对

1
2
3
4
5
6
7


lhm.put(1, null); 
lhm.put(null, "abc");  
lhm.put(1000, "aaa");
lhm.put(2, "bbb");
lhm.put(30000, "ccc");

lhm.put(30000, "ddd");  //更新覆盖ccc

`remove`

删除某一个K-V对

1

lhm.remove(2);

`size`

返回数据大小

1

lhm.size()

遍历

 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


public static void traverseByEntry(LinkedHashMap<Integer,String> lhm)
{
  System.out.println("============Entry迭代器遍历==============");
  Integer key;
  String value;
  Iterator<Entry<Integer, String>> iter = lhm.entrySet().iterator();
  while(iter.hasNext()) {
      Map.Entry<Integer, String> entry = iter.next();
      // 获取key
      key = entry.getKey();
      // 获取value
      value = entry.getValue();
      //System.out.println("Key:" + key + ", Value:" + value);
  }
}


public static void traverseByKeySet(LinkedHashMap<Integer,String> lhm)
{
  System.out.println("============KeySet迭代器遍历=============="); 
  Integer key;
  String value;
  Iterator<Integer> iter = lhm.keySet().iterator();
  while(iter.hasNext()) {
      key = iter.next();        
      // 获取value
      value = lhm.get(key);
      //System.out.println("Key:" + key + ", Value:" + value);
  }
}

5.4 `TreeMap`

基于红黑树的Map
可以根据key的自然排序或者compareTo方法进行排序输出

定义和初始化

1
2


import java.util.TreeMap;
TreeMap<Integer,String> tm =new  TreeMap<Integer,String>();

`clear`

清空数据

1

tm.clear();

`containsValue`

是否包含某一个值

1

tm.containsValue("aaa")

`containsKey`

是否包含某一个Key

1

tm.containsKey(30000)

`get`

根据Key获取相应的值

1

tm.get(30000)

`put`

增加新的K-V对

1
2
3
4
5
6
7


tm.put(1, null); 
//tm.put(null, "abc");  编译没错，运行报空指针异常 
tm.put(1000, "aaa");
tm.put(2, "bbb");
tm.put(30000, "ccc");

tm.put(30000, "ddd");  //更新覆盖ccc

`remove`

删除某一个K-V对

1

tm.remove(2);

`size`

返回数据大小

1

tm.size()

遍历

 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



public static void traverseByEntry(TreeMap<Integer,String> tm)
{
  System.out.println("============Entry迭代器遍历==============");
  Integer key;
  String value;
  Iterator<Entry<Integer, String>> iter = tm.entrySet().iterator();
  while(iter.hasNext()) {
      Map.Entry<Integer, String> entry = iter.next();
      // 获取key
      key = entry.getKey();
      // 获取value
      value = entry.getValue();
      //System.out.println("Key:" + key + ", Value:" + value);
  }
}


public static void traverseByKeySet(TreeMap<Integer,String> tm)
{
  System.out.println("============KeySet迭代器遍历=============="); 
  Integer key;
  String value;
  Iterator<Integer> iter = tm.keySet().iterator();
  while(iter.hasNext()) {
      key = iter.next();        
      // 获取value
      value = tm.get(key);
      //System.out.println("Key:" + key + ", Value:" + value);
  }
}

5.5 `Properties`

继承自Hashtable
可以将K-V对保存在文件中
适用于数据量少的配置文件
load：加载原文件中所有的K-V对
store：将所有的K-V对写入到文件中
getProperty：获取某一个Key所对应的Value
setProperty：写入一个K-V对

 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


import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Enumeration;
import java.util.Properties;

//关于Properties类常用的操作
public class PropertiesTest {
    //根据Key读取Value
    public static String GetValueByKey(String filePath, String key) {
        Properties pps = new Properties();
        try {
            InputStream in = new BufferedInputStream (new FileInputStream(filePath));  
            pps.load(in); //所有的K-V对都加载了
            String value = pps.getProperty(key);
            //System.out.println(key + " = " + value);
            return value;
            
        }catch (IOException e) {
            e.printStackTrace();
            return null;
        }
    }
    
    //读取Properties的全部信息
    public static void GetAllProperties(String filePath) throws IOException {
        Properties pps = new Properties();
        InputStream in = new BufferedInputStream(new FileInputStream(filePath));
        pps.load(in); //所有的K-V对都加载了
        Enumeration en = pps.propertyNames(); //得到配置文件的名字
        
        while(en.hasMoreElements()) {
            String strKey = (String) en.nextElement();
            String strValue = pps.getProperty(strKey);
            //System.out.println(strKey + "=" + strValue);
        }
        
    }
    
    //写入Properties信息
    public static void WriteProperties (String filePath, String pKey, String pValue) throws IOException {
        File file = new File(filePath);
      if(!file.exists())
      {
        file.createNewFile();
      }
      Properties pps = new Properties();
        
      InputStream in = new FileInputStream(filePath);
      //从输入流中读取属性列表（键和元素对） 
      pps.load(in);
      //调用 Hashtable 的方法 put。使用 getProperty 方法提供并行性。  
      //强制要求为属性的键和值使用字符串。返回值是 Hashtable 调用 put 的结果。
      OutputStream out = new FileOutputStream(filePath);
      pps.setProperty(pKey, pValue);
      //以适合使用 load 方法加载到 Properties 表中的格式，  
      //将此 Properties 表中的属性列表（键和元素对）写入输出流  
      pps.store(out, "Update " + pKey + " name");
      out.close();
    }
    
    public static void main(String [] args) throws IOException{
      System.out.println("写入Test.properties================");
      WriteProperties("Test.properties","name", "12345");
      
      System.out.println("加载Test.properties================");
      GetAllProperties("Test.properties");
      
      System.out.println("从Test.properties加载================");
      String value = GetValueByKey("Test.properties", "name");
      System.out.println("name is " + value);
    }
}


/**
 * 
 * 运行结果：
 * 写入Test.properties================
 * 加载Test.properties================
 * 从Test.properties加载================
 * name is 12345
 * 
 */

6 工具类

6.1 `Arrays`

排序 `sort/parallelSort`

对数组排序

 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 static void testSort() {
  Random r = new Random();
  int[] a = new int[10];
  for(int i=0;i<a.length;i++) {
    a[i] = r.nextInt();
  }
  System.out.println("===============测试排序================");
  System.out.println("排序前");
  for(int i=0;i<a.length;i++) {
    System.out.print(a[i] + ",");
  }
  System.out.println();
  System.out.println("排序后");
  Arrays.sort(a);
  for(int i=0;i<a.length;i++) {
    System.out.print(a[i] + ",");
  }
  System.out.println();   
}
/**
 * 
 * ===============测试排序================
 * 排序前
 * -1132207311,138314395,-1589844698,21086905,-1280289820,-1685791626,-680547355,572504069,1029156267,1833937878,
 * 排序后
 * -1685791626,-1589844698,-1280289820,-1132207311,-680547355,21086905,138314395,572504069,1029156267,1833937878,
 * 
 */

查找 `binarySearch`

从数组中查找一个元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


public static void testSearch() {
  Random r = new Random();
  int[] a = new int[10];
  for(int i=0;i<a.length;i++)
  {
    a[i] = r.nextInt();
  }
  a[a.length-1] = 10000;
  System.out.println("===========测试查找============");
  System.out.println("10000 的位置是" + Arrays.binarySearch(a, 10000));
}

/**
 * 
 * ===========测试查找============
 * 10000 的位置是9
 * 
 * 
 */

批量拷贝 `copyOf`

从源数组批量复制元素到目标数组

 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


public static void testCopy() {
  Random r = new Random();
  int[] a = new int[10];
  for(int i=0;i<a.length;i++)
  {
    a[i] = r.nextInt();
  }
  int[] b = Arrays.copyOf(a, 5);
  System.out.println("===========测试拷贝前五个元素============");
  System.out.print("源数组：");
  for(int i=0;i<a.length;i++)
  {
    System.out.print(a[i] + ",");
  }
  System.out.println();
  System.out.print("目标数组：");
  for(int i=0;i<b.length;i++)
  {
    System.out.print(b[i] + ",");
  }
  System.out.println();
}
/**
 * 
 * ===========测试拷贝前五个元素============
 * 源数组：670811887,1566520826,-514867056,-1186107665,129679533,149113219,-956323326,89906597,-1450389055,944799102,
 * 目标数组：670811887,1566520826,-514867056,-1186107665,129679533,
 * 
 * 
 * 
 * 
 */

批量赋值 `fill`

对数组进行批量赋值，

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


public static void testFill() {
  int[] a = new int[10];
  Arrays.fill(a, 100);
  Arrays.fill(a, 2, 8, 200);
  System.out.println("===========测试批量赋值============");
  System.out.print("数组赋值后：");
  for(int i=0;i<a.length;i++)
  {
    System.out.print(a[i] + ",");
  }
  System.out.println();
}
/**
 * 
 * ===========测试批量赋值============
 * 数组赋值后：100,100,200,200,200,200,200,200,100,100,
 * 
 * 
 */

等价性比较 `equals`

判定两个数组内容是否相同

1
2
3
4
5
6
7
8
9


public static void testEquality() {
  int[] a = new int[10];
  Arrays.fill(a, 100);
  int[] b = new int[10];
  Arrays.fill(b, 100);    
  System.out.println(Arrays.equals(a, b)); //true
  b[9] = 200;
  System.out.println(Arrays.equals(a, b)); //false
}

6.2 `Collections`

处理对象是Collection及其子类

排序：对`List`进行排序，`sort`

1
2


// 排序
Collections.sort(list);

搜索 `binarySearch`

从List中搜索元素

1

Collections.binarySearch(list, 12);

批量赋值 `fill`

对List批量赋值

1

Collections.fill(list, 100); //全部赋值为100

最大 `max`、最小 `min`

查找集合中最大/最小值

1
2
3
4


//最大值
Collections.max(list);
//最小值
Collections.min(list);

反序 `reverse`

将List反序排列

1

Collections.reverse(list); //翻转不需要用到排序

6.3 对象比较

对象排序需要遵循一定的规则。Integer对象可以自然按数值大小进行排序。而普通的自定义对象无法排序。因此，普通自定义对象需要实现Comparable接口，按照CompareTo方法所规定的原则进行排序。

对象实现Comparable接口（需要修改对象类）
- compareTo方法： > 返回 1，== 返回 0，< 返回 -1
- Arrays和Collections在进行对象sort时，自动调用该方法。
新建Comparator（适用于对象类不可更改的情况）
- compare方法： > 返回 1，== 返回 0，< 返回 -1
- Comparator比较器将作为参数提交给工具类的sort方法

  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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110


//Person.java
import java.util.Arrays;

public class Person implements Comparable<Person> {
  String name;
  int age;

  public String getName() {
    return name;
  }

  public int getAge() {
    return age;
  }

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

  public int compareTo(Person another) {
    int i = 0;
    i = name.compareTo(another.name); // 使用字符串的比较
    if (i == 0) {
      // 如果名字一样,比较年龄, 返回比较年龄结果
      return age - another.age;
    } else {
      return i; // 名字不一样, 返回比较名字的结果.
    }
  }

  public static void main(String... a) {
    Person[] ps = new Person[3];
    ps[0] = new Person("Tom", 20);
    ps[1] = new Person("Mike", 18);
    ps[2] = new Person("Mike", 20);

    Arrays.sort(ps);
    for (Person p : ps) {
      System.out.println(p.getName() + "," + p.getAge());
    }
  }
}

/**
 * 
 * 输出结果：
 * Mike,18
 * Mike,20
 * Tom,20
 * 
 */

//Person2Comparator.java
import java.util.Arrays;
import java.util.Comparator;

public class Person2Comparator  implements Comparator<Person2> {
  public int compare(Person2 one, Person2 another) {
    int i = 0;
    i = one.getName().compareTo(another.getName());
    if (i == 0) {
      // 如果名字一样,比较年龄,返回比较年龄结果
      return one.getAge() - another.getAge();
    } else {
      return i; // 名字不一样, 返回比较名字的结果.
    }
  }

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Person2[] ps = new Person2[3];
    ps[0] = new Person2("Tom", 20);
    ps[1] = new Person2("Mike", 18);
    ps[2] = new Person2("Mike", 20);

    Arrays.sort(ps, new Person2Comparator());
    for (Person2 p : ps) {
      System.out.println(p.getName() + "," + p.getAge());
    }
  }
}

//Person2.java

public class Person2 {
  private String name;
  private int age;
  public String getName() {
    return name;
  }
  public int getAge() {
    return age;
  }

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

/**
 * 
 * 输出结果：
 * Mike,18
 * Mike,20
 * Tom,20
 * 
 */

目录

[Java核心技术] Java数据结构

1 数组

1.1 定义和初始化

1.2 数组索引

1.3 数组遍历

1.4 多维数组

2 JCF(Java Collection Framework)

3 List

3.1 ArrayList

声明和初始化

add

remove

遍历

3.2 LinkedList

声明和初始化

add

remove

遍历

ArrayList与LinkedList对比

3.3 Vector

声明和初始化

add

remove

遍历

4 集合Set

4.1 Java中的集合接口Set

4.2 HashSet

声明和初始化

add 添加一个元素

clear 清除整个HashSet

contains 判定是否包含一个元素

remove 删除一个元素

size 大小

retainAll 计算两个集合交集

遍历

4.3 TreeSet

声明和初始化

add 添加一个元素

clear 清除整个TreeSet

contains 判定是否包含一个元素

remove 删除一个元素

size 大小

遍历

4.4 LinkedHashSet

声明和初始化

add

remove

clear

contains

size

遍历

4.5 异同点

5 映射Map

5.1 Hashtable

定义和初始化

clear

contains/containsValue

containsKey

get

put

remove

size

遍历

5.2 HashMap

定义和初始化

clear

containsValue

containsKey

get

put

remove

size

遍历

5.3 LinkedHashMap

定义和初始化

clear

containsValue

containsKey

get

3 `List`

3.1 `ArrayList`

`add`

`remove`

3.2 `LinkedList`

`add`

`remove`

`ArrayList`与`LinkedList`对比

3.3 `Vector`

`add`

`remove`

4 集合`Set`

4.1 `Java`中的集合接口`Set`

4.2 `HashSet`

`add` 添加一个元素

`clear` 清除整个`HashSet`

`contains` 判定是否包含一个元素

`remove` 删除一个元素

`size` 大小

`retainAll` 计算两个集合交集

4.3 `TreeSet`

`add` 添加一个元素

`clear` 清除整个`TreeSet`

`contains` 判定是否包含一个元素

`remove` 删除一个元素

`size` 大小

4.4 `LinkedHashSet`

`add`

`remove`

`clear`

`contains`

`size`

5 映射`Map`

5.1 `Hashtable`

`clear`

`contains/containsValue`

`containsKey`

`get`

`put`

`remove`

`size`

5.2 `HashMap`

`clear`

`containsValue`

`containsKey`

`get`

`put`

`remove`

`size`

5.3 `LinkedHashMap`

`clear`

`containsValue`

`containsKey`

`get`

`put`

`remove`

`size`

5.4 `TreeMap`

`clear`

`containsValue`

`containsKey`

`get`

`put`

`remove`

`size`

5.5 `Properties`

6.1 `Arrays`

排序 `sort/parallelSort`

查找 `binarySearch`

批量拷贝 `copyOf`

批量赋值 `fill`

等价性比较 `equals`

6.2 `Collections`

排序：对`List`进行排序，`sort`

搜索 `binarySearch`

批量赋值 `fill`

最大 `max`、最小 `min`

反序 `reverse`