Java数据结构基础——集合和映射表

ゝ一世哀愁。 2022-05-20 10:00 177阅读 0赞

*   *  1. 引言
     *  2. 集合
        
         *  2.1 HashSet
         *  2.2 LinkedHashSet
         *  2.3 TreeSet
     *  3. 比较集合和线性表的性能
     *  4. 映射表
        
         *  4.1 HashMap
         *  4.2 LinkedHashMap
         *  4.3 TreeMap
     *  5. 总结

## 1. 引言 ##

集合(set)是一个用于存储和处理**无重复元素**的高效数据结构。映射表(map)类似于目录，提供了使用键值快速查询和获取值的功能。

## 2. 集合 ##

可以使用集合的三个具体类HashSet、LinkedHashSet、TreeSet来创建集合。Set接口扩展了Collection接口，它没有引入新的方法或常量，只是规定Set的实例不包含重复的元素。

### 2.1 HashSet ###

> java.util.HashSet<E>

HashSet()
    HashSet(c: Collection<? extends E>)
    HashSet(initialCapacity: int)
    HashSet(initialCapacity: int, loadFactor: float)      //负载因子

默认情况下，初始容量为16而负载系数是0.75，当元素个数超过了容量与负载系数的成绩，容量会自动翻倍。HashSet类用于存储互不相同的任何元素，考虑到效率的因素，添加到散列集中的对象必须以一种正确分散散列码的方式来实现hashCode方法。  
如果两个对象相等，那么这两个对象的散列码必须一样。两个不相等的对象可能会有相同的散列码。

### 2.2 LinkedHashSet ###

> java.util.LinkedHashSet<E>  
> 构造方法同上

LinkedHashSet用一个链表实现来扩展HashSet类，他支持对集合内的元素排序，HashSet没有排序，LinkedHashSet中的元素可以按照插入集合的顺序提取。

### 2.3 TreeSet ###

> java.util.TreeSet<E>

TreeSet()
    TreeSet(c: Collection<? extends E>)
    TreeSet(comparator: Comparator<? super E>)
    TreeSet(s: SortedSet<E>)

只要对象是可以互相比较的，就可以将他们添加到一个TreeSet当中

## 3. 比较集合和线性表的性能 ##

在无重复元素进行排序方面，集合比线性表更加高效。线性表通过索引来访问元素方面非常有用，集合不支持索引，因为集合是无序的。  
如下程序用于检测50000次查询与删除时集合和线性表的性能。

public class TestBenchmarkofSetandList {
      static final int N = 50000;
    
      //返回50000次查找随机数的时间
      public static long getTestTime(Collection<Integer> c) {
        long startTime = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
          c.contains((int)(Math.random() * 2 * N));
        }
        return System.currentTimeMillis() - startTime;
      }
    
      //返回50000次删除元素的时间
      public static long getRemoveTime(Collection<Integer> c) {
        long startTime = System.currentTimeMillis();
        for(int i = 0; i < N; i++) {
          c.remove(i);
        }
        return System.currentTimeMillis() - startTime;
      }
    
      public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < N; i++) {
          list.add(i);
        }
        Collections.shuffle(list);
    
        //测试HashSet性能
        Collection<Integer> set1 = new HashSet<>(list);
        System.out.println("Member test time for hash set is " 
          + getTestTime(set1) + " milliseconds");
        System.out.println("Remove test time for hash set is " 
          + getRemoveTime(set1) + " milliseconds");
    
        //测试LinkedHashSet性能
        Collection<Integer> set2 = new LinkedHashSet<>(list);
        System.out.println("Member test time for linked hash set is " 
          + getTestTime(set2) + " milliseconds");
        System.out.println("Remove test time for linked hash set is " 
          + getRemoveTime(set2) + " milliseconds");
    
        //测试TreeSet性能
        Collection<Integer> set3 = new TreeSet<>(list);
        System.out.println("Member test time for tree set is " 
          + getTestTime(set3) + " milliseconds");
        System.out.println("Remove test time for tree set is " 
          + getRemoveTime(set3) + " milliseconds");
    
        //测试ArrayList性能
        Collection<Integer> set4 = new ArrayList<>(list);
        System.out.println("Member test time for array list is " 
          + getTestTime(set4) + " milliseconds");
        System.out.println("Remove test time for array list is " 
          + getRemoveTime(set4) + " milliseconds");
    
        //测试LinkedList性能
        Collection<Integer> set5 = new LinkedList<>(list);
        System.out.println("Member test time for linked hash set is " 
          + getTestTime(set5) + " milliseconds");
        System.out.println("Remove test time for linked hash set is " 
          + getRemoveTime(set5) + " milliseconds");    
      }  
    }
    
    /* 执行结果： Member test time for hash set is 9 milliseconds Remove test time for hash set is 7 milliseconds Member test time for linked hash set is 9 milliseconds Remove test time for linked hash set is 13 milliseconds Member test time for tree set is 12 milliseconds Remove test time for tree set is 14 milliseconds Member test time for array list is 2795 milliseconds Remove test time for array list is 885 milliseconds Member test time for linked hash set is 4646 milliseconds Remove test time for linked hash set is 2173 milliseconds */

在实验中可以明显看到集合比线性表的效率高很多。

## 4. 映射表 ##

映射表(map)是一种依照键/值对来存储元素的容器。可以使用三种具体的类来创建一个映射表：HashMap、LinkedHashMap、TreeMap。他提供了通过键快速获取、删除和更新键/值对的功能。映射表中不能有重复的键，一个键和他的对应值构成一个条目并保存在映射表中。

> <<interface>>  
> java.util.Map<K,V>

clear: void                                    //从该映射表中删除所有元素
    containsKey(key: Object): boolean              //如果包含指定键的条目返回true
    containsValue(value: Object): boolean          //如果map中包含一个或多个键映射到指定值，返回true
    entrySet(): Set<Map.Entry<K,V>>                //返回一个包含了该映射表中条目的集合
    keySet(): Set<K>                               //返回包含了所有键的集合
    values(): Collection<V>                        //返回所有值组成的合集
    get(key: Object): V                            //返回指定键对应的值
    put(key: K, value: V): V                       //将一个条目放入映射表中
    putAll(m: Map<? extends K, ? extends V>): void //将m中所有的条目添加到映射表中
    remove(key: Object): V                         //删除指定键对应的条目
    size(): int                                    //返回条目的数目
    ......

更新方法包括clear、put、putAll、remove，方法put指定的键如果原来就存在，则原来的值将被替代并返回原来的值。  
查询方法包括containsKey、containsValue、isEmpty和size。  
方法entrySet()返回一个所有条目的集合。这些条目是Map.Entry

getKey(): K
    getValue(): V
    setValue(value: V): void

### 4.1 HashMap ###

> java.util.HashMap

HashMap()
    HashMap(initialCapacity: int, loadFactor: float)          //负载因子
    HashMap(m: Map<? extends K,? extends V>)

对于定位一个值、插入一个条目以及删除一个条目而言，HashMap是高效的。

### 4.2 LinkedHashMap ###

> java.util.LinkedHashMap

LinkedHashMap()
    LinkedHashMap(m: Map<? extends K, ? extends V>)
    LinkedHashMap(initialCapacity: int,loadFactor: float,accessOrder: boolean)//负载系数，访问顺序

LinkedHashMap用链表实现来扩展HashMap类，他支持条目的排序。默认无参构造方法按插入顺序排序，第三个有参构造方法按访问顺序排序。

### 4.3 TreeMap ###

> java.util.TreeMap

TreeMap()
    TreeMap(m: Map<? extends K,V extends V>)
    TreeMap(c: Comparator<? extens V>)

TreeMap类在遍历排好序的键时是很高效的。默认无参构造方法假定键的类实现了Comparable接口，则可以使用Comparable中的compareTo方法。要使用比较器，必须使用第三个构造方法。  
**备注：**  
\- 如果不需要保持映射表中元素的顺序，就用HashMap；如果需要保持插入顺序或访问顺序，就用LinkedHashMap；如果需要按照键排序就用TreeMap。  
\- 映射表是线程不安全的，安全的使用有三种方式：Hashtable、ConcurrentHashMap、Synchronized，具体讲解参考文章“[如何线程安全的使用HashMapMap][HashMapMap]”

## 5. 总结 ##

*  集合存储的是不重复的元素，映射表中存储的是键/值对。
 *  Map将键映射到元素上，键类似于索引，Map接口提供了查询、更新以及获取值的集合以及键的集合的方法。
 *  Java合集框架支持三种类型的集合：HashSet、LinkedHashSet、TreeSet。
 *  Java合集框架支持三种类型的映射表：HashMap、LinkedHashMap、TreeMap。

参考资料：《Java语言程序设计（进阶篇）》

[HashMapMap]: http://www.importnew.com/21396.html