Collection
├List
│ ├LinkedList
│ ├ArrayList
│ └Vector
│ └Stack 栈
└Set接口
└HashSet (使用HashMap实现)
└SortedSet接口
└TreeSet (使用TreeMap实现)
├Map
└Hashtable
└HashMap
└LinkedHashMap
└WeakHashMap
├SortedMap
└TreeMap
public interface SortedSet<E> extends Set<E> public interface SortedMap<K,V> extends Map<K,V> public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
问题1：HashMap与Hashtable的区别
Hashtable是Dictionary类的子类，HashMap是Map接口的一个实现类
1.HashTable的方法是同步的，HashMap未经同步
2.HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。
3.HashTable有一个contains(Object value)，功能和containsValue(Object value)功能一样。
4.HashTable使用Enumeration，HashMap使用Iterator。
问题2：如何HashMap同步？
法1、Collections.synchronizedMap(Map m)
法2、使用ConcurrentHashMap
详述：
LinkedList：
private transient Entry<E> header = new Entry<E>(null, null, null);
public LinkedList() {
header.next = header.previous = header;
}
private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
//默认的添加动作，可以看到这个方法是把新元素添加 到表尾
public boolean add(E e) {
addBefore(e, header); //加到头结点之前 ，即表尾
return true;
}
//默认的删除动作是删除链表的第一个元素，所以说在默认情况下，LinkedList其实扮*演的是一个队列的角色
public E remove() {
return removeFirst();
}
public E get(int index) {
return entry(index).element;
}
private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
newEntry.previous.next = newEntry; //将新结点与前后结点相连接
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
// 根据给定的索引值离表头近还是离表尾近决定从头还是从尾开始遍历
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry<E> e = header;
if (index < (size >> 1)) { //如果较靠近有表头
for (int i = 0; i <= index; i++)
e = e.next;
} else { //较靠近表尾
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
//从表头开始遍历，返回此元素在表中的第一个位置
public int indexOf(Object o) {
int index = 0;
if (o==null) { //如果传入的元素是null，则不能调用 eqauls方法进行比较
for (Entry e = header.next; e != header; e = e.next) {
if (e.element==null)
return index;
index++;
}
} else {
for (Entry e = header.next; e != header; e = e.next) {
if (o.equals(e.element))
return index;
index++;
}
}
return -1;
}
注意entry的循环：
for (Entry e = header.previous; e != header; e = e.previous) {}
新节点的创建：
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
此时新加节点已知道其前后节点，但其前节点并不知道后节点发生变化，后节点也不知道前节点发生变化，所以分别将新节点赋给他们。
HashMap:
put -> addEntry(新建一个Entry)
get
getEntry
//get与getEntry的区别在于一个返回的是Entry对象，一个返回的是Entry对象中的Value
LinkedHashMap:
put -> addEntry(重写)
新建一个Entry,然后将其加入header前
e.addBefore(header)
get -> 调用HashMap的getEntry - recordAccess(重写)
Hashtable：
public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable
抽象类Dictionary 已过时，新的实现应该实现 Map 接口，而不是扩展此类。
HashMap:
//public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
LinkedHashMap:
//其实LinkedHashMap几乎和HashMap一样，不同的是它定义了一个Entry<K,V> header，这个header不是放在Table里，它是额外独立出来的。LinkedHashMap通过继承hashMap中的Entry<K,V>,并添加两个属性Entry<K,V> before,after,和header结合起来组成一个双向链表，来实现按插入顺序或访问顺序排序。
//public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
private transient Entry<K,V> header;
private final boolean accessOrder;
void init() {
header = new Entry<K,V>(-1, null, null, null);
header.before = header.after = header;
}
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
private void remove() {
before.after = after;
after.before = before;
}
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
}
//遍历
//for (Entry e = header.after; e != header; e = e.after)
public boolean containsValue(Object value) {
if (value==null) {
for (Entry e = header.after; e != header; e = e.after)
if (e.value==null)
return true;
} else {
for (Entry e = header.after; e != header; e = e.after)
if (value.equals(e.value))
return true;
}
return false;
}
//LinkedHashMap的get()方法调用的是HashMap的getEntry - recordAccess(重写)
//get与getEntry的区别在于一个返回的是Entry对象，一个返回的是Entry对象中的Value
3、
相关推荐
java集合分类总结.doc
JAVA集合类总结[整理].pdf
对java集合类的总结。 包括性能，类图。
今天在网上搜索了一下，发现一篇关于java集合的博文，里面整理得非常好， 特意copy过来和大家分享一下
Java集合类包下的多个集合类是我们项目开发中常用的类，由于存在大量的方法，若没有一个清晰的总结框图，很难灵活使用，通过该总结，你会发再其实该包下的接口并非我们想象的那么复杂...
对java集合类的部分总结，希望对大家有用，呵呵
总结Java标准类库的容器类； 容器类库是你每天都会用到的工具，它能使程序更简介，更强大并且更搞笑。
Java中集合类用法总结Java中集合类用法总结.pdf
java的各种集合类的总结，以及实例讲解。
java集合类知识总结--思维导图文件xmind xmind文件类型 总结了java常用集合相关问题 包括map、set、list、数组等
JAVA集合类用法总结 概括了 java 的所有集合的用法 MAP SET List 等
java集合类面试题总结
JAVA中集合类的总结
经常用到的集合类的一个总结
JAVA中集合类一些常用类的总结
java集合类HashMap总结共7页.pdf.zip
JAVA集合类的一些总结 collection,vector,arraylist,list,hashtable...
java集合类ArrayList总结共9页.pdf.zip
Java集合类总结 Java集合详解1：一文读懂ArrayList,Vector与Stack使用方法和实现原理 Java集合详解2：Queue和LinkedList Java集合详解3：Iterator，fail-fast机制与比较器 Java集合详解4：HashMap和HashTable Java...