Java 容器类及其数据结构

 

线程安全与否

安全：Vector、HashTable、StringBuffer

不安全：ArrayList、LinkedList、HashMap、StringBuilder 

非线程安全容器变得线程安全 
使用

• Listlist=Collections.synchronizedList(new ArrayList());
• set = Collections.synchronizedSet(new HashSet());
• map = Collections.synchronizedMap(new HashMap())

序列化可以使得线程变安全。

容器类 UnsupportedOperationException

List list = Arrays.aslIst(); 引起的异常，可以参考

https://blog.****.net/liu_005/article/details/74091805

原因：List 、Collection 这种父类没有实现add（）方法，抛出了异常，而其最底层的子类ArrayList ，LinkedList实现了，所以不会由问题。

数据结构

ArrayList 底层数组

LinkedList 双向链表

HashMap ：key-value封装成一个Entry对象存储到一个Entry数组中，位置（数组下标）由key的哈希值与数组长度计算而来。

TreeMap/TreeSet ：

只要带Tree的容器结构，其对象必须实现Comparable 接口，否则会报错

java.lang.ClassCastException: com.sjh.collection.People cannot be cast to java.lang.Comparable

比如定义个People 实体类：

public class People {

    int age;

    public int getAge() {
        return age;
    }

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

    public People(int age) {
        this.age = age;
    }
}

 测试代码：

 TreeSet<People> peopleTreeSet = new TreeSet<>();
        peopleTreeSet.add(new People(1));
        peopleTreeSet.add(new People(3));
        peopleTreeSet.add(new People(2));
        Iterator<People> peopleIterator = peopleTreeSet.iterator();
        while (peopleIterator.hasNext()){
            System.out.println(peopleIterator.next().getAge());
        }

运行时  peopleTreeSet.add(new People(1)); 就会报错，如前面的提示所说。另外，注意基本数据结构比较特殊，它们默认实现了Comparable 接口，所以没有问题。

 

Set ：维护一个Map来存储数据的，利用Map结构key值唯一性，HashSet、TreeSet分别默认维护一个HashMap、TreeMap

HashSet ：哈希散列集，底层由HashMap支持的，主要使用hashCode()和equal()方法确保Key值不可重复性来保证元素的唯一性

 

 

散列——为速度而散列

 

散列：可以参考书 数据结构，里面有专门一章节讲解这个，如果想要搞明白可以看书，这里简单写一些东西。

理想的散列表数据结构时一个包含一些项的固定大小的数组；数组里面存放的是项的关键信息，这个称为 key。理想的情况是一个项对应一个数组的位置，但是由于数组固定，而集合是不固定的，如果二者一一分配，就叫完美散列，但集合数据多于数组长度之后，就会存在冲突，多个项会到相同index位置上。而散列的关键问题就是解决这个冲突？于是就产生了不同的算法，有分离链接法、双散列等等。这就是整个散列的原因和中心思想。