Java Collections 框架中的接口,有很多方法被标注为可选的(optional),这意味着允许具体的实现类不实现这些方法,被调用到的时候直接抛出一个 UnsupportedOperationException 异常。
同时 Java 也提供了一系列的通用实现(general purpose implementations),这些实现适用于所有通用的场景,它们实现了对应接口的所有方法,下面这个表格总结的所有的通用实现:
接口
|
HashTable
|
Resiable Array
|
Balanced Tree
|
Linked List
|
Hash Table + LinkedList
|
Set
|
HashSet
|
|
TreeSet |
|
LinkedHashSet
|
List
|
|
ArrayList
|
|
LinkedList
|
|
Deque
|
|
ArrayDeque
|
|
LinkedList
|
|
Map
|
HashMap
|
|
TreeMap |
|
LinkedHashMap
|
下面逐个分析一下各个通用实现中比较巧妙的技术细节。
ArrayList
ArrayList 使用可伸缩数组实现 List 接口。除了不支持同步之外,跟 Vector 非常类似。
内部数据存储结构:数组。
数组容量增长规则:默认增长到原来容量的 1.5 倍,如果所需的量比这个值大(addAll 一个 Collections 的时候可能会出现这样的情况),则按需增长。
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
ArrayDeque
ArrayDeque 使用可伸缩数组实现双端数组接口,是非线程安全的,在栈的场景下它的性能优于 Stack,在队列的场景下优于 LinkedList。
内部采用循环数组结构,并保持数组的大小是 2 的 n 次幂。
容量增长的规则:增长到原来容量的 2 倍。
初始容量分配算法
/** * Allocates empty array to hold the given number of elements. * * @param numElements the number of elements to hold */ private void allocateElements(int numElements) { int initialCapacity = MIN_INITIAL_CAPACITY; // Find the best power of two to hold elements. // Tests "<=" because arrays aren't kept full. if (numElements >= initialCapacity) { initialCapacity = numElements; initialCapacity |= (initialCapacity >>> 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); initialCapacity++; if (initialCapacity < 0) // Too many elements, must back off initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements } elements = new Object[initialCapacity]; }
扩容算法
/** * Doubles the capacity of this deque. Call only when full, i.e., * when head and tail have wrapped around to become equal. */ private void doubleCapacity() { assert head == tail; int p = head; int n = elements.length; int r = n - p; // number of elements to the right of p int newCapacity = n << 1; if (newCapacity < 0) throw new IllegalStateException("Sorry, deque too big"); Object[] a = new Object[newCapacity]; System.arraycopy(elements, p, a, 0, r); System.arraycopy(elements, 0, a, r, p); elements = a; head = 0; tail = n; }
插入节点定位方式:/** * Inserts the specified element at the front of this deque. * * @param e the element to add * @throws NullPointerException if the specified element is null */ public void addFirst(E e) { if (e == null) throw new NullPointerException(); elements[head = (head - 1) & (elements.length - 1)] = e; if (head == tail) doubleCapacity(); }
HashMap
HashMap 是基于哈希表的 Map 接口实现,它跟 Hashtable 很像,不同点是它不是线程安全的,另外它支持 key 或 value 为空。
哈希桶是以 2 的 n 次幂数组为存储。
哈希方案是 key 的 hashCode 高低位重合。
解决冲突的方案是冲突节点少于 8 个采用链表,否则采用红黑树。
扩容的方案是每次扩容哈希桶数量为原来的二倍,扩从时间点多数在新增一个节点之后。
扩容时机:可以指定一个负载因子(loadFactor),默认是 0.75,当元素数量超过 capacity * loadFactor 时,就开始扩容。
hash 算法:
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
查找节点方法:
/** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */ final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 先找哈希桶的第一个节点 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) // 如果是树型节点,遍历树查找节点 return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { // 链表结构的节点,依次遍历链表查找 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
具体扩容算法:
/** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 对于树型节点,分裂之,具体算法跟下面的类似 else { // preserve order Node<K,V> loHead = null, loTail = null; // 因为扩容算法是容量翻倍,因此扩容前的一个桶对应扩容后的两个桶 Node<K,V> hiHead = null, hiTail = null; // loHead 和 hiHead 分别对应扩容后的两个桶 Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
HashSet
HashSet 整体借用 HashMap 来实现,实际上就是内部引用了一个 HashMap 实例。
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { static final long serialVersionUID = -5024744406713321676L; private transient HashMap<E,Object> map; // 内部引用了一个 HashMap 实例 // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); /** * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has * default initial capacity (16) and load factor (0.75). */ public HashSet() { map = new HashMap<>(); }
添加元素的算法:
public boolean add(E e) { return map.put(e, PRESENT)==null; // 仅仅对 HashMap 实例的简单调用 }
TreeMap
TreeMap 基于红黑树实现 NavigableMap 接口,它是非线程安全的。
TreeSet
内部默认借用 TreeMap 实现。
LinkedList
LinkedList 内部封装了一个双向链表,此外没什么特别的。
一个优化点是根据下标访问元素的时候是先判断元素是在链表中的前部还是后部,从而决定是先序遍历还是后序遍历。
LinkedHashMap
内部封装了一个 HashMap 加一个双向链表。HashMap 通过继承的方式复用,双向链表用户维护迭代器的元素访问顺序,默认按照 key 的插入顺序迭代,也可以按照 key 的访问顺序迭代。
按照 key 的访问顺序迭代的方式适用于实现基于 LRU 策略的缓存系统,实现思路是继承 LinkedHashMap 并覆写 removeEldestEntry 方法,具体可以参考这个帖子:
LinkedHashSet
LinkedHashSet 是要支持按序迭代访问,它内部聚合了一个 LinkedHashMap 来实现它的功能。
实现上有个巧妙的地方可以学习:它对 LinkedHashMap 的聚合是通过继承 HashSet 来实现的,具体代码是给 HashSet 新增了一个内部构造方法:
/** * Constructs a new, empty linked hash set. (This package private * constructor is only used by LinkedHashSet.) The backing * HashMap instance is a LinkedHashMap with the specified initial * capacity and the specified load factor. * * @param initialCapacity the initial capacity of the hash map * @param loadFactor the load factor of the hash map * @param dummy ignored (distinguishes this * constructor from other int, float constructor.) * @throws IllegalArgumentException if the initial capacity is less * than zero, or if the load factor is nonpositive */ HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); }
这个方法有两点值得注意,一个是方法的可见域是默认,另一个是加了一个哑参数用于跟其他构造函数做区分。
相关推荐
通用集合 C#通用集合的Java实现
泛型与集合 使用 进行初步翻译. 将利用碎片时间进行整理和校对,完整的时间段适合做其他需要大量思考的事,如果你有兴趣欢迎提交PR。 TODO 数据校对 目录 2.4 获取和放置原则 2.5 数组 ...6.5 广告中
CommonsCollections,又是一个重量级的东西,为Java标准的CollectionsAPI提供了相当好的补充。我不知道其他人,就我自己而言,让我用 java.util.Collection及其子类,加上java.util.Collections类提供的操作方法,...
Java通用后台管理系统源码 源码描述: 一、特色功能 1、采用Spring MVC的静态加载缓存功能,在首页将Javascript文件、CSS文件和图片等静态资源文件加载进来放进内存,极大提高ExtJS的加载速度。 2、三种皮肤主题:...
Collection接口在Java 类库中有很多具体的实现。 Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式, 其直接继承接口有List与Set。 Collection ├List │├LinkedList │├ArrayList │└Vector ...
2.2.3 Java中的数组 2.3 绝对不要清除对象 2.3.1 作用域 2.3.2 对象的作用域 2.4 新建数据类型:类 2.4.1 字段和方法 2.5 方法、自变量和返回值 2.5.1 自变量列表 2.6 构建Java程序 2.6.1 名字的可见性 2.6.2 使用...
Apache Commons Collections的使用指南,该jar包提供了多数集合的线程安全版本,以及增强了大多数的集合功能,送给那些不想重复发明轮子的人.
2.2.3 Java中的数组 2.3 绝对不要清除对象 2.3.1 作用域 2.3.2 对象的作用域 2.4 新建数据类型:类 2.4.1 字段和方法 2.5 方法、自变量和返回值 2.5.1 自变量列表 2.6 构建Java程序 2.6.1 名字的可见性 2.6.2 使用...
给定一个C语言函数,要求实现在java类中进行调用。 45.如何获得数组的长度? 46.访问修饰符“public/private/protected/缺省的修饰符”的使用 47.用关键字final修饰一个类或者方法时,有何意义? 48.掌握类和...
“工欲善其事,必先利其器”,在Java程序开发过程中,很多算法(比如:MD5加密算法)、很多数据结构(比如链表LinkedList)已经实现并且大多放在类库的java.util包中,程序员只需要了解各种工具的功能就可以直接调用...
通用排序Java中使用泛型实现的各种排序算法注意:这是一个有趣的项目。 如果您希望熟悉排序算法或Java泛型,那么您可能会发现此项目很有趣。 如果要在实际项目中执行排序,建议您使用Java的内置Collections.sort()...
系统可作为OA、网站、电子政务、ERP、CRM、APP后台等基于B/S架构的应用软件系统的快速开发框架。 一、特色功能 ...7、采用Google Guava Collections,性能高于Apache Collections。 更多下载查看文档。
标量数组的问题Java模板不支持将标量类型作为通用参数。 与列表或集合等集合接口一起使用的Java代码不适用于数组。 一些库提供了使用对象数组的方法。 这些方法是通用类型和内置类型,例如int,boolean,long,...
声明方法的存在而不去实现它的类被叫做抽象类(abstract class),它用于要创建一个体现某些基本行为的类,并为该类声明方法,但不能在该类中实现该类的情况。不能创建abstract 类的实例。然而可以创建一个变量,其...
2.2.3 Java中的数组 2.3 绝对不要清除对象 2.3.1 作用域 2.3.2 对象的作用域 2.4 新建数据类型:类 2.4.1 字段和方法 2.5 方法、自变量和返回值 2.5.1 自变量列表 2.6 构建Java程序 2.6.1 名字的可见性 2.6.2 使用...
2.2.3 Java中的数组 2.3 绝对不要清除对象 2.3.1 作用域 2.3.2 对象的作用域 2.4 新建数据类型:类 2.4.1 字段和方法 2.5 方法、自变量和返回值 2.5.1 自变量列表 2.6 构建Java程序 2.6.1 名字的可见性 2.6.2 使用...
1、采用ExtJS 4.2.1.883无限制版本,放心用于网站开发。 2、ExtJS富文本编辑器增加修改信息。 3、ExtJS的HtmlEditor的图片文件...7、采用Google Guava Collections,性能高于Apache Collections。 更多下载查看文档。
容器是Java编程的一大利器,常用的类是:ArrayList (List)作为可变长数组、HashMap(Map)用来建立查找表,Set很少用,只在HashMap的使用中连带用过一些。通过对这两个类的熟悉,能够将List、Set和Map三大类的基本用法...
2.2.3 Java中的数组 2.3 绝对不要清除对象 2.3.1 作用域 2.3.2 对象的作用域 2.4 新建数据类型:类 2.4.1 字段和方法 2.5 方法、自变量和返回值 2.5.1 自变量列表 2.6 构建Java程序 2.6.1 名字的可见性 2.6.2 使用...
系统可作为OA、网站、电子政务、ERP、CRM、APP后台等基于B/S架构的应用软件系统的快速开发框架。 一、特色功能 ...7、采用Google Guava Collections,性能高于Apache Collections。 更多下载查看文档。