Java 核心技术卷I - 集合

Posted on   |   In   |   visited:  

集合

队列接口

1
2
3
4
5
6
interface Queue<E>
{
    void add(E element);
    E remove();
    int size();
}

两个实现：
ArrayDeque 循环数组队列，高效但容量有限
LinkedList 链表队列

集合类的几本接口是Collection

1
2
3
4
5
interface Collection<E> {
    boolean add(E element);// 添加成功，返回true
    Iterator<E> iterator(); ／／返回一个实现了Iterator接口的对象，依次访问集合中的每个元素。
    ...
}

链表

LinkedList 实现了List接口

1
2
3
4
5
6
7
List<String> staff = new  LinkedList<>();
staff.add('a'); // 添加到链表尾部
staff.add('b');
Iterator iter = staff.iterator();
String first = iter.next();
String second = iter.next();
iter.remove(); // 删除second元素

如果希望添加到链表中间位置，使用子接口列表迭代器ListIterator，其中包含add方法：

1
2
3
void add(E element);
E previous();
boolean hasPrevious();

例如

1
2
3
4
5
6
List<String> staff = new  LinkedList<>();
staff.add('a'); // 添加到链表尾部
staff.add('b');
ListIterator iter = staff.listIterator();
String first = iter.next();
iter.add('c'); // 在第一个元素后面添加一个元素

LinkedList 获取某个元素

LinkedList 提供了一个用来访问某个特定元素的get方法，staff.get(n); 每次都要从链表的头部重新开始搜索。

而列表迭代器实现了一个方法：
staff.listIterator(n)将返回一个迭代器，这个迭代器指向索引为n的元素前面的位置。
然后调用iter.next产生与staff.get(n)同一个元素。

数组

LinkedList实现了List接口，List有两种访问方式：
一种是使用迭代器，一种是使用get 和set方法随机访问某个元素。后者不适合链表。

Q1: ArrayList 和 Vector的区别？

散列表

快速查找所需要的对象
用链表数组实现
散列冲突： 相对应的桶被占满
装填因子（load factor）：决定何时对散列表进行再散列，如75%，说明表中75%的位置已经填入元素，这个表会用双倍的桶数自动进行再散列。
HashSet: 实现了基于散列表的集合，implements Set

1
2
3
4
5
6
7
8
9
10
Set<String> set = new HashSet<>();
Scanner in = new Scanner(System.in);
while(in.hasNext()){
    String w = in.next();
    set.add(w);
}
Iterator<String> iter = set.iterator();
while(iter.hasNext()){
    System.out.println(iter.next());
}

创建 HashSet(int initialCapacity, float loadFactor) 指定容量和装填因子（0.0～1.0之间的数值）的空散列集。

树集

TreeSet 有序集合
排序是用红黑树实现的
implements SortedSet()

Q2: 红黑树？算法导论里有提到

如果树中包含n个元素，查找新元素的正确位置平均需要logn (底为2)次比较，因此将一个元素添加到TreeSetz中要比添加到HashSet中慢。

1
2
TreeSet() //构造一个空树集
TreeSet(Collection<? extends E> elements)构造一个树集，并将集合中的所有元素添加到树集中。

队列与双端队列

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
java.util.Queue
boolean add(E element)
boolean offer(E element)
如果队列没有满，将给定元素添加到这个队列的尾部并返回true，如果满了，第一个方法抛出IllegalStateException, 第二个方法返回false。
E remove()
E poll()
删除队列头部元素
E element()
E peek()
返回头部元素，但不删除
java.util.Deque
与Queue类似
void addFirst(E element)
void addLast(E element)
boolean offerFirst(E element)
boolean offerLast(E element)
添加到队列的头部或者尾部
remove和poll类似
E getFirst()
E getLast()
E peekFirst()
E peekLast()
java.util.ArrayDeque
ArrayDeque()
ArrayDeque(int initialCapacity)
用初始容量16或给定的初始容量构造一个无限双端队列

优先级队列

使用堆（自我调整的二叉树）实现。
可以按人意顺序插入，却按排序的顺序检索，默认返回队列中最小的元素。

1
2
3
4
5
PriorityQueue<TmpClass> pq = new PriorityQueue<>();
pq.add(new TmpClass(1,'first'));
PriorityQueue(int initialCapacity, Comparator<? super E> c)
构造一个优先级队列，并用指定的比较器对元素进行排序

映射表

两个通用实现：HashMap 和 TreeMap。 实现了Map接口。

HashMap:

1
2
3
4
5
6
7
8
9
Set<K> keySet() 返回键集合
Collection<K> values()  返回值集合
Set<Map.Entry<K,V>> entrySet 返回键／值集合
for example：
for (Map.entry<String, Employee> entry: staff.entrySet()) {
    String key = entry.getKey();
    Employee value = entry.getValue();
}

HashMap(int initialCapacity, float loadFactor) 指定容量和装填因子（0.0～1.0之间的数值）的空散列映射表。

TreeMap:
有序映射表

Q3: TreeMap的使用场景？

专用集和映射表类

WeakHashMap
LinkedHashSet和LinkedHashMap,用来记住插入元素项的顺序。
EnumSet是一个枚举类型元素集的高效实现。由于枚举类型只有有限个实例，所以EnumSet内部用位序列实现，如果对应的值在集中，则相应的位被置1。
EnumMap: 键类型位枚举类型的映射表。
Java 类库支持下面几种具体类
LinkeList
ArrayList
ArrayDeque
HashSet
TreeSet
PriorityQueue
HashMap
TreeMap

批操作

1
2
3
4
5
6
7
8
9
10
11
12
// 求两个集合的交集
Set<String> result = new HashSet(a);
result.retains(b);
集合与数组之间的转换
String[] values = ;
HashSet<String> staff = new HashSet<>(Arrays.asList(values))
将集合转换为数组：Object[] values = staff.toArray();
无法改变类型。  
另外一种转换方法：String[] values = staff.toArray(new String[0]);
staff.toArray(new String[staff.size()]);

算法

终于到了算法的部分了！

排序

java 的排序将所有元素转入一个数组，并使用一种归并排序的变体对数组进行排序，然后，再将排序后的序列复制回列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
List<String> staff = new LinkedList();
Collections.sort(staff)  // 默认生序
// 如果想降序
Collections.sort(staff, Collections.reverseOrder());
// 其他方式排序
Comparator<Item> itemComparator = new Comparator<Item>() 
{
    public int compare(Item a, Item b) 
    {
        return a.num - b.num;
    }
};
Collections.sort(staff, itemComparator);
// 按照其他方式逆序排序
Collections.sort(staff, Collections.reverseOrder(itemComparator));

集合中的归并排序比快排要慢一些，但是优点：稳定，即不需要交换相同的元素。

混排

随机混排列表中的元素：

1
Collections.shuffle(staff);

复杂度分析：
sort的时间复杂度是O(nlogn),n为列表长度。
shuffle 时间复杂度是O(n a(n)), a(n) 是访问元素的平均时间。

Q4: 实现集合的shuffle算法？

二分查找

排好序的集合使用下面的二分查找，提供参数：集合和要查找的元素

1
2
index = Collections.binarySearch(c, element);
index = Collections.binarySearch(c, element, comparator);

如果返回数值大于等于0，则表示匹配对象的索引。

1
c.get(index) ＝ element；

如果返回负值，则表示没有匹配的元素。但是可以利用返回值计算应该将element 插入到集合的哪个位置，以保持集合的有序性。插入的位置是

1
2
3
insertPoint = -index - 1;
if (index<0)
    c.add(-i-1, element);

注：只有采用随机访问，二分查找才有意义。如果必须利用迭代方式一次次遍历链表的一半元素来找到中间位置的元素，二分查找就完全失去了优势。
因此，如果为binarySearch算法提供一个链表，它将自动的变为线性查找。

时间复杂度：O(a(n)logn), a(n) 是访问元素的平均时间。

简单算法

1
2
3
4
5
6
7
8
9
10
11
12
min(Collection<T> elements)  
max
copy(List<? super T> to, List<T> from);
fill(List<? super T> l, T value); // 将列表中所有位置设置为相同的值
addAll(Collection<? super T> c, T ...values);
replaceAll(List<T> l, T oldValue, T newValue);
indexOfSubList(List<?> l, List<?> s);
swap(List<?> l, int i, int j); // 交换给定偏移量的两个元素
reverse（List<?> l);
rotate(List<?> l, int d) // 旋转列表中的元素，将索引i的条目移动到位置(i + d) % l.size()
frequency(Collection<?> c, Object o); // 返回c中与对象o相同的元素个数
disjoint(Collection<?> cl, Collection<?> c2); // 如果两个集合没有共同的元素，返回true

编写自己的方法，尽量使用接口

遗留的集合

  1. Hashtable(t小写) 与HashMap的作用一样，方法是同步的，对同步性没有要求的情况下，应该使用HashMap
  2. 枚举
    Enumeration两个方法，hasMoreElements 和 nextElement

  3. 属性映射表
    Properties

    1
    2
    3
    4
    getProperty(String key)
    getProperty(String key, String defaultValue)没找到返回默认值
    load(InputStream in) // 从InputStream加载属性映射表
    store(OutputStream out, String commentString) // 把属性映射表存储到OutputStream

  4. 栈 Stack
    push, pop, peek

  5. 位集 Bitset 

    1
    2
    3
    4
    5
    6
    7
    get(i)  // 第i位位于“开”状态，返回true  
    set(i)  // 设置为“开”
    clear(i) // 设置为"关”
    and
    or
    xor
    andNot

    应用，找素数

找出100以内的素数
素数定义：质数，又称素数，指在一个大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（也可定义为只有1和本身两个因数的数）。
使用Java.util.BitSet求素数的算法：
例如要找100以内的素数，
1，声明一个BitSet bs，第0,1位置false；其余位是true。
2，从2开始遍历bs，如果是true就进行内循环遍历。
3，内循环遍历：从外向内环i开始遍历bs，每次增长一个i（这个很重要），把内循环j在bs中的位置成false。
代码如下

1
2
3
4
5
6
7
8
for(int i=0;i<bs.size();i++){
 if(bs.get(i)){
  //内循环遍历
  for(int j=2*i;j<bs.size();j+=i){
   bs.set(j, false);
  }
 }
}

完整的代码

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
package com;  
  
import java.util.BitSet;  
  
public class mianTestSix {  
  
    /**  
     * @param args  
     */  
    public static void main(String[] args) {  
        BitSet bs=new BitSet(100);  
        initBitSet(bs);  
        findSushuBitSet(bs);  
        printSushuBitSet(bs);  
    }  
      
    //第0,1位置成false，其余全部是true.  
    public static void initBitSet(BitSet bs){  
        for(int i=0;i<bs.size();i++){  
            if(i==0||i==1){  
                bs.set(i, false);  
            }else{  
                bs.set(i, true);  
            }  
        }  
    }  
    //处理数据，找到素数  
    public static void findSushuBitSet(BitSet bs){  
        for(int i=0;i<bs.size();i++){  
            if(bs.get(i)){  
                //内循环遍历  
                for(int j=2*i;j<bs.size();j+=i){  
                    bs.set(j, false);  
                }  
            }  
              
        }  
    }  
    //位是1的是素数，打印  
    public static void printSushuBitSet(BitSet bs){  
        StringBuffer buf=new StringBuffer();  
        int num=0;  
        for(int i=0;i<100;i++){  
            if(bs.get(i)){  
                buf.append(i+",");  
                num++;  
            }  
              
            if((num+1)%20==0&&num!=0){  
                buf.append("\n");  
            }  
        }  
        System.out.println(buf.toString());  
    }  
      
  
}