-
iterator可用来遍历Set和Lisi集合,但是ListIterator只能用来遍历List集合
-
Iterator对集合只能是向前遍历,ListIterator既可以前向也可以后向
boolean hasNext(); E next(); default void remove() { throw new UnsupportedOperationException("remove"); } default void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); while (hasNext()) action.accept(next()); } -
ListIterator实现了Iterator接口，并包含其他的功能,比如：增加元素，替换元素，
获取前一个和后一个元素的索引，等等
//反向遍历列表时，如果此列表迭代器包含更多元素,则返回true boolean hasPrevious(); //返回列表中的前一个元素,并将光标位置向后移动，如果迭代中没有上一个元素，抛出 NoSuchElementException异常 E previous(); void set(E e); void add(E e);**注意：**remove和set不是针对当前游标进行操作，而是针对最后一次的next()和previous()调用
ArrayList和LinkedList都实现了List接口，它们有以下的不同点：
-
ArrayList是基于索引的数据接口，它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。
-
LinkedList是以元素列表的形式存储它的数据，每一个元素都和它的前一个和后一个元素链接在一起，在这种情况下，查找某个元素的时间复杂度是O(n)。
-
相对于ArrayList，LinkedList的插入，添加，删除操作速度更快，因为当元素被添加到集合任意位置的时候，不需要像数组那样重新计算大小或者是更新索引。
-
LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。
- Vector的实现与ArrayList类似，但是使用了synchronized进行同步，因此开销就比ArrayList要大，访问速度更慢。最好使用ArrayList而不是Vector，因为同步操作完全可以由程序员自己来控制；
- Vector每次扩容请求其大小的2倍(也可以通过构造函数设置增长的容量)，而ArrayList是1.5倍。
- 两者都是继承自Collection接口
- List特点：元素有放入顺序，元素可重复。支持for循环，也就是通过下标来遍历，也可以用迭代器，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变
- Set特点：元素无放入顺序，元素不可重复，重复元素会被覆盖掉。Set只能用迭代，因为它无序，无法用下标来取得想要的值。检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
- ArrayList的底层实现是一个动态增长的数组。List list=new ArrayList<>()这样创建一个list时，会创建一个大小为10的数组。如果超过数组的长度时，需要使用grow()方法进行扩容，新容量的大小为：int newCapacity = oldCapacity + (oldCapacity >> 1)，也就是旧容量的1.5倍。扩容操作需要调用Arrays.copryOf()把原数组整个复制到新数组中，这个操作代价很高。
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);
}
- ArrayList中存放顺序和添加顺序是一致的，并且可重复元素
- HashSe基于哈希表实现，它的底层是HashMap,
public HashSet() {
map = new HashMap<>();
}
- HashSet不能够存储相同的元素，并且存储是无序的。
- HashSet实现了Set接口，仅存储对象；HashMap实现了Map接口，存储的是键值对
- HashSet底层是用HashMap实现存储的，HashSet封装了一系列HashMap的方法，依靠HashMap来存储元素值(利用HashMap的Key键进行存储)，而value值默认为Object对象，所以HashSet也不允许出现重复值，判断标准和HashMap判断标准相同，两个元素的hashCode相等并且通过equals()方法返回true.
两者都实现了Map接口，不同点：
- HashMap允许键和值是null，而Hashtable不允许键或者值是null
- Hashtable使用synchronized来进行同步，而HashMap不是，因此，HashMap更适合于单线程环境，而Hashtable适合于多线程环境
- HashMap提供了可供应用迭代的键的集合，因此，HashMap是快速失败的(fail-fast)。另一方面，Hashtable提供了对键的列举(Enumeration)
- 一般认为Hashtable是一个遗留的类
- HashSet是由一个hash表来实现的，因此，它的元素是无序的。add()，remove()，contains()方法的时间复杂度是O(1)。
- TreeSet是由一个树形的结构来实现的，它里面的元素是有序的。因此，add()，remove()，contains()方法的时间复杂度是O(n)
TreeSet的底层基于TreeMap实现，而TreeMap是基于红黑树实现的
public TreeSet() {
this(new TreeMap<E,Object>());
}
- TreeMap和TreeSet都是有序的集合，也就是说他们存储的值都是排好序的
- 两者都是非同步集合，因此他们不能在多线程之间共享
- 最主要的区别就是TreeSet和TreeMap分别实现Set和Map接口
- TreeSet只存储一个对象，而TreeMap存储两个对象key和value(仅仅key对象有序)
- TreeSet中不能有重复对象，而TreeMap中可以存在
- HashMap:桶数组+链表+红黑树
- TreeMap:红黑树
- HashMap:Node和TreeNode
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
- TreeMap:只是红黑树
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
}
- HashMap适用于在Map中插入、删除和定位元素，TreeMap适用于按自然顺序或自定义顺序遍历键(key)
- HashMap通常比TreeMap快一点(哈希表和树的数据结构使然)
- HashMap的结果是没有排序的，而TreeMap输出的结果是排好序的
- Collection是集合类的顶级接口，继承于它的接口主要有Set和List
- Collections是针对集合类的一个帮助类，它提供了一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作
java中的HashMap是以键值对(key-value)的形式存储元素的。HashMap需要一个hash函数，它使用hashcode()和equals()方法来向集合/从集合中添加和检索元素。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
当调用put()方法的时候,HahMap会计算key的hash值,然后把键值对存储在集合中合适的索引上。如果Key已经存在了,value会被更新成新值
Map<String,String> map=new HashMap<>();
//添加元素
map.put("劫","吾所成之事,不可逆也");
map.put("亚索","长路漫漫,唯剑作伴");
map.put("烬","黎明中的花朵");
map.put("烬","科比式外交");
Set<Map.Entry<String,String>> set=map.entrySet();
Iterator<Map.Entry<String,String>> iterator1=set.iterator();
while(iterator1.hasNext()){
System.out.println(iterator1.next());
}
//亚索=长路漫漫,唯剑作伴
//劫=吾所成之事,不可逆也
//烬=科比式外交
这时候map的size()变成了3,因为最后一个put时替换了前面的值
实现原理：由于HashMap是一个线程不安全的容器，主要体现在容量大于总量*负载因子发生扩容时会出现环形链表从而导致死循环，因此需要支持线程安全的并发容器ConcurrentHashMap
JDK1.8实现
在JDK1.8中抛弃了原有的Segment分段锁，而采用了CAS+synchronized来保证并发安全性
put操作：
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
// key 和 value 不能为空
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
// f = 目标位置元素
Node<K,V> f; int n, i, fh;// fh 后面存放目标位置的元素 hash 值
if (tab == null || (n = tab.length) == 0)
// 数组桶为空，初始化数组桶（自旋+CAS)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 桶内为空，CAS 放入，不加锁，成功了就直接 break 跳出
if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// 使用 synchronized 加锁加入节点
synchronized (f) {
if (tabAt(tab, i) == f) {
// 说明是链表
if (fh >= 0) {
binCount = 1;
// 循环加入新的或者覆盖节点
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
// 红黑树
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}