Java的集合与散列

程序员文章站 2022-03-15 20:34:35

...

之所以很多程序员认为Java简单，很大一部分原因是Jdk帮java程序员提供了集合与散列数据结构。作为Java程序员很有必要好好学习一下，最近几天对其作了复习，所以就有了此文。

Java集合

框架主要接口

java.util.Collection
java.util.List
java.util.Queue
java.util.Set

集合中List,Queue它的实现类底层结构为数组、链表。而对于Set集合它的实现子类实现完全依赖于Java的散列。
Collection接口继承了Iterable,拥有一个迭代器，所以Collection集合的子类均是可以遍历的。

在集合中有几个重要的实现类：

java.util.ArrayList 它的实现结构为数组，初始容量为10,每次写入数据之后即判断是否需要扩容。如果需要扩容则进行1.5的长度扩容，并将相应的数组内容进行复制到新数组内。由于它的实现结构为数组可以通过数组的下标进行快速的数据访问，数组结构也决定了java.util.ArrayList可以随机访问时间为O(1).
java.util.LinkedList它的实现结构为链表.LinkedList内部节点构建有两个节点引用，一个是指向当前节点的前一个节点；另一个是指向当前节点的后一个节点。所以LinkedList为一个双向链表即从前向后遍历；或者从后向前遍历均可。它的节点访问只能通过每个节点逐个遍历进行比较取出对应节点值.
二者的比较如下：

类名	实现结构	增操作	删操作	改操作	查操作
java.util.ArrayList	数组	在尾部增加节点很容易O(1),但是在头部或中间增加节点需要进行相应的节点值后移，难度较大	删除节点也需要进行后面的节点前移,难度较大，但是尾部删除较容易	这个相对比较容易，只需两次O(1)操作，即一次查找，一次写入	比较容易，不需遍历，O(1)操作
java.util.LinkedList	双向链表	首部，尾部增加较易一次接链的操作，如果在中间增加需要一次节点遍历	难度与增操作一样	难度与增操作一样	需要节点便利，不能随机访问

对于如下

主要提供的接口

java.util.Map

重要实现类为:

java.util.HashMap 它的数据存储结构在jdk8之前为数组+链表。HashMap初始化的时候数组初始长度为16.数据的存储与获取首先对于key时行hash值计算，然后与数组长度取模，得到的值作为数据存储在数组的下标位置。对于不同的key，hash值相同，则会计算出相同的数组下标，这就是所谓的hash碰撞，对于数种情况，HashMap使用链表结来存储这些值。极端情况下，存储的全是key的hash值相同的数据，这时HashMap实质即为一个单向链表，它的获取数据的性能会极速下降。为了防止单个数组位置上的链表长度过长，在jdk8对于进行了优化，当链表的长度达一定值时，更换数据存储结构，转而使用红黑树结构进行存储。此时HashMap的存储结构即为数组+红黑树。
java.util.TreeMap它的实现为红黑树。一致性哈希可以使用TreeMap作为底层的存储结构实现.
java.util.HashTable它与java.util.HashMap的区别，前者实现了线程安全，而后者不是.