Set

Posted on | In

Java类库帮助我们在程序设计中实现传统的数据结构。

1. 链表

在Java中，数组和数字列表都有一个很大缺陷，从数组中间位置删除一个元素要付很大代价，其原因是数组中处于被删除之后的所有元素都要向数组前端移动，在数组中插入一个元素也是如此。链表（linked list）完美地解决了这个问题。

  1. 链表将每个对象存放在独立的节点中，每个节点还放着下一个节点的引用。在Java中，所有链表都是双向链接的。

  2. 链表与泛型集合的重要区别是，链表是一个有序集合，每个对象位置十分重要。LinkedList.add方法将对象添加到链表尾部，但是常常需要将元素添加到链表中间。实现这一功能需要迭代器的帮助。只有对自然有序的集合使用迭代器添加元素才有意义。集合类库中，提供了ListIterator方法，其中包含add方法

interface ListIterator<E> extends Iterator<E>
{
    void add(E element);
    ... 
    E previous()
    boolean hasPrevious()
}

  1. 与next方法一样，previous方法返回越过对象
    Add方法在迭代器位置之前添加一个新对象，下面的代码将越过链表中的第一个元素，并在第二个元素前添加Juliet

    List<String> staff = new LinkedList<>();
staff.add("Amy");
staff.add("Bob");
staff.add("Carl");
ListIterator<String> iter = staff.listIterator();
iter.next();
next.add("Juliet");

  2. set方法用一个新的元素取代调用next或previous方法返回上一个元素。

ListIterator<String> iter = list.listIterator();
String oldValue = iter.next;
iter.set(newValue);// set the first element to newValue
  1. 链表不支持快速访问元素。如果要查看链表中第n个元素，必须要越过n-1个元素，没有捷径可走。尽管如此，LinkedList类还是提供了一个用来访问你的get方法：
    LinkedList<String> list = ...;
String obj = list.get(n);
    当然，这种方法的效率很低，如果发现了正在使用这种方法，可能对于要解决的问题使用了错误的数据结构。

2. 数组

在Java中有两种访问元素的协议，一种是用迭代器，另一种是用get，set方法随机地访问每个元素。后者不适用于链表，但对数组却很有用。集合类库提供了大家熟悉的ArrayList类，这个类也实现了List接口。ArrayList封装了一个动态再分配的数组对象。

3. 散列集

散列集可以快速查找元素，缺点是无法控制元素的出现次序，适用于不知索引快速查找对象的情况。它们将按照有利于其操作目的的原则组织数据。

  1. 散列表（hash table）：散列表为每个对象计算一个整数，称为散列码（hash code）。散列码是由对象的实例域产生的一个整数。具有不同数据域的对象将产生不同散列码。

  2. hashCode 方法：hashCode方法应该返回一个整型数值（也可为负），并合理的组织实例域的散列码，以便能让各个不同的对象产生的散列码更均匀。

    public class Employee
{
    public int hashCode(){
        return 7 * name.hashCode()
        + 11 * new Double(salary).hashCode()
        + 13 * hireDay.hashCode();
    }
}

    不过还可以做得更好，用Object.hashCode方法来使null安全。如果参数为null，返回0，否则返回对参数调用hashCode的结果。

    public int hashCode(){
    return Object.hash(name,salary,hireDay);
}

  3. 查找/插入元素

    1. 在Java中散列表用链表数组实现，每个列表称为桶。要想查找表中对象的位置，需要先计算他的散列码，然后与桶的总数取余，所得结果就是保存这个元素的桶的索引。例如，某对象散列码为76268，有128个桶，对象应该保存在第108号桶中。若该桶没有其他元素，则直接插入。若该桶被占满，这种现象称为散列冲突，这时新对象与桶中所有对象比较，查看该对象是否已经存在。

    2. 桶数设定: 如果大致知道有多少个元素要插入散列表中，就可以设置初始桶数。通常将桶数设置为预计元素个数的 70% ~ 150%。标准类库中，使用的桶数是2的幂，默认值为16。在JavaSE8中，桶满时会从链表变为平衡二叉树。

  4. HashSet类
    Java类库提供了一个HashSet类，它实现基于散列表的集，可以用add方法添加元素。contains方法被重新定义，用来快速查看某个元素是否出现在集中。