【文章】链表的简要 - 黑马程序员技术交流社区

链表将每个对象存放在独立的节点中，每个节点还存放着序列中下一个节点的引用。在java中，所有链表都是双向链表——即每个节点还存放着上一个节点的引用。

很轻松地就可以从链表中删除一个元素，只需要对被删除元素附近的结点更新一个即可。

LinkedList 的数据结构就是链表，使用它的 listIterator 方法可以获得 ListIterator 迭代器，从而对链表进行操作。

如果在某个迭代器修改集合时，另一个迭代器对其进行遍历，就可能出现 Concurrent ModificationException 异常。因此，多个迭代器同时操作时，一定要注意。

链表不支持快速地随机访问。如果要查看链表中第 n 个元素，必须从头开始，越过 n-1 个元素。如果需要从用整数索引访问元素时，尽量不用链表。

尽管如此，LinkedList 还是提供了 get 方法用来访问特定元素，只是这个方法的效率并不太高。

[Java] 纯文本查看 复制代码



for(int i = 0; i< list.size(); i++){



    System.out.println(list.get(i));



}

get 方法做了微小的优化，如果索引大于 size()/2 就从列表尾端开始搜索元素。

列表迭代器的 nextIndex 和 previousIndex 方法，可以返回当前位置的索引。

list.listIterator(n) 将返回一个迭代器，它指向索引为 n 的元素前面的位置。也就是说，调用 next 与调用 list.get(n) 会获取到同一个元素。这个迭代器的效率比较低。

如果链表中的元素比较少，就不必担心 get 和 set 方法的开销。使用链表的唯一理由是尽可能地减少在列表中间插入或删除元素所付的代价。如果只有少数几个元素，可以使用 ArrayList 存储。

散列表为每个对象计算一个整数，成为散列码（hash code），每个对象的 hash code 是不一样的。如果要自定义类，就要负责实现 hasCode 方法。注意，自己实现的 hashCode 方法和 equals 方法应该兼容，即 a.equals(b) 为 true，那么 a 和 b 的 hasCode 应该一样。

在 Java 中，hast table 用链表数组实现。每个列表被称为桶（bucket）。想要查找表中对象的位置，就要先计算它的 hash code，然后与桶的总数取余，所得到的结果就是保存这个元素的桶的索引。例如，如果某个对象的 hash code 为 76268，并且有 128 个桶，对象应该保存在第 108 号桶中。

如果这个桶中没有其他元素，这个对象可以直接插入桶中。如果桶被占了，这种情况被称为散列冲突（hash collision）。这时，需要用新对象与桶中的所有对象进行比较，查看这个对象是否已经存在。如果散列码是合理且随机分布的，桶的数目也足够大，需要比较的次数就会很少。

如果想要更多地控制散列表的运行性能，就要指定一个初始的桶数。桶数是用于收集具有相同散列值的桶的数目。如果要插入到散列表中的元素太多，就会增加冲突的可能性，降低运行性能。

如果大致知道最终会有多少个元素要插入到散列表中，就可以设置桶数。通常，将桶数设置为预计元素个数的 75%～150%。标准类库使用的桶数是 2 的幂，默认值是 16。

如果散列表太满，就需要再散列（rehashed），即创建一个双倍桶数的表，然后将所有的元素插入到这个新表，丢弃原来的表。装填因子（load factor）决定何时再散列。默认是 0.75，即表中超过 75% 的位置已经填入元素，就进行再散列。

散列表迭代器将依次访问所有的桶，由于散列表将元素分散在表的各个位置上，所以访问它们的顺序是随机的。

Java 集合类库中的 set 类型就是散列表的数据结构，它没有重复元素，每次在添加对象之前，都会查找是否在已经存在。HashSet 实现了基于散列表（hash table）的集。

在创建 HashSet 和 HashMap 的时候，最好预计一下容量。如果容量不足，要再散列的话，就有点影响性能了。

在 Guava 库中，Maps.newHashMapWithExpectedSize() 和 Sets.newHashSetWithExpectedSize() 这两个方法，就是创建指定大小的 HashMap 和 HashSet。

有序集合，底层结构是红黑树（red-black tree）。每次插入元素，会按照排序放在正确的位置。元素的访问顺序也是排序的顺序，而不是插入的顺序。

树集假定插入的元素实现了 Comparable 接口，这个接口定义了一个方法：

如果 a 与 b 相等，返回 a.compareTo(b) 返回 0；如果返回正数，表示 a 位于 b 之后；如果返回负数，表示 a 位于 b 之前。

如果在树集中放置自定义的对象，这个对象必须实现 Comparable 接口来自定义排序的方式。

[Java] 纯文本查看 复制代码

class Student implements Comparable<Student>{



  public int compareTo(Student other){



    return age - other.age;



  }



}

另一种方法是将 Comparator 对象传递给 TreeSet 构造器来告诉树集怎么排序。

[Java] 纯文本查看 复制代码

class SutdentComparator implements Comparator<Student>{



  public int compare(Sutdent a, Sutdent b){



    return (a.age).compareTo(b.age);



  }



}

[Java] 纯文本查看 复制代码

SortedSet<Student> sortByAge = new TreeSet<>(new SutdentComparator());



1



或者，直接定义一个匿名内部类传递给 TreeSet：







SortedSet<Student> sortByAge = new TreeSet<>(new Comparator<Student>() {



  @Override



  public int compare(Sutdent a, Sutdent b){



    return (a.age).compareTo(b.age);



  }



});