2017网站开发合同下载,wordpress 顶部高度,高米店网站建设公司,做类似360手赚那样的网站说一下双列集合#xff0c;顶级接口是Map#xff0c;实现类有HashMap、LinkedHashMap、TreeMap、HashTable等#xff0c;使用键值对的格式存储数据#xff0c;键不可以重复#xff0c;值可以重复。接下来对实现类做一下详细介绍。 HashMap是最常用的Map集合#xff0c;它… 说一下双列集合顶级接口是Map实现类有HashMap、LinkedHashMap、TreeMap、HashTable等使用键值对的格式存储数据键不可以重复值可以重复。接下来对实现类做一下详细介绍。 HashMap是最常用的Map集合它所依赖的数据结构是散列表还有红黑树添加元素时现根据添加键值对的key去得到对应的hash值然后根据hash值和数组的长度确定key在数组中对应的下标位置然后根据散列是否冲突的原理进行数据添加或者替换具体分析如下添加的元素不会进行排序并且是无序集合。当获取元素时也是根据key键所对应的hash值进行查找的依赖于数组进行查找可以达到O1的效果HashMap可以被克隆和序列化是线程不安全的集合。具体分析如下 //HashMap对象可被克隆、被序列化
public class HashMapK,V extends AbstractMapK,V implements MapK,V, Cloneable, Serializable {//-------------------------------------- 变量 -------------------------------------////哈希表transient NodeK,V[] table;transient SetMap.EntryK,V entrySet;//map中键值对的个数集合的容量transient int size;//修改次数transient int modCount;//阈值。要调整大小的下一个大小值(容量*负载系数)int threshold;//哈希表的负载因子final float loadFactor;//默认的初始容量必须是2的n次幂//计算结点插入位置时才会取决于hash值并且保证hash值小于数组长度static final int DEFAULT_INITIAL_CAPACITY 1 4;//最大容量static final int MAXIMUM_CAPACITY 1 30;//默认的加载因子static final float DEFAULT_LOAD_FACTOR 0.75f;//使用树而不是列表的计数阈值当向至少有这么多节点的容器中添加元素时容器被转换为树。其实一般用到的不多static final int TREEIFY_THRESHOLD 8;//调整大小的计数阈值。操作次数应小于UNTREEIFY_THRESHOLDstatic final int UNTREEIFY_THRESHOLD 6;//将链表树状化的最小哈希表容量就是哈希表中达到一定数据时才有必要将链表转化成树static final int MIN_TREEIFY_CAPACITY 64;//基本hash bin结点就是哈希表中链表中的结点static class NodeK,V implements Map.EntryK,V {final int hash;//记录hash值final K key;//键V value;//值NodeK,V next;//下一个结点Node(int hash, K key, V value, NodeK,V next) {this.hash hash;this.key key;this.value value;this.next next;}public final K getKey() { return key; }public final V getValue() { return value; }public final String toString() { return key value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue value;value newValue;return oldValue;}public final boolean equals(Object o) {if (o this)return true;if (o instanceof Map.Entry) {Map.Entry?,? e (Map.Entry?,?)o;if (Objects.equals(key, e.getKey()) Objects.equals(value, e.getValue()))return true;}return false;}}//-------------------------------------- 静态的公用方法------------------////重要函数计算hash值static final int hash(Object key) {int h;//key.hashCode()返回key的哈希码值与哈希值的高16位进行异或运算//使得位置尽量分散return (key null) ? 0 : (h key.hashCode()) ^ (h 16);}//只有传入的对象的运行时类型实现了Comparable才会被返回否则返回nullstatic Class? comparableClassFor(Object x) {//判断当前对象是否实现了比较器接口if (x instanceof Comparable) {Class? c; Type[] ts, as; Type t; ParameterizedType p;if ((c x.getClass()) String.class)return c;if ((ts c.getGenericInterfaces()) ! null) {for (int i 0; i ts.length; i) {if (((t ts[i]) instanceof ParameterizedType) ((p (ParameterizedType)t).getRawType() Comparable.class) (as p.getActualTypeArguments()) ! null as.length 1 as[0] c)return c;}}}return null;}//只有传入的对象x和kc的类型相同时才进行比较SuppressWarnings({rawtypes,unchecked}) // for cast to Comparablestatic int compareComparables(Class? kc, Object k, Object x) {return (x null || x.getClass() ! kc ? 0 :((Comparable)k).compareTo(x));}//返回一个最接近2的幂并且大于cap的整数static final int tableSizeFor(int cap) {int n cap - 1;n | n 1;n | n 2;n | n 4;n | n 8;n | n 16;return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;}//-------------------------------------- 构造方法-------------------////根据初始大小和负载因子创建实例public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor);this.loadFactor loadFactor;//将最接近2的幂并且大于initialCapacity的整数作为阈值this.threshold tableSizeFor(initialCapacity);}//根据初始大小和负载因子创建实例public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR;}//-------------------------------------- 功能方法-------------------////集合中键值对个数public int size() {return size;}
//-------------------------------------- 获取方法 ------------------// //根据键获取值public V get(Object key) {NodeK,V e;return (e getNode(hash(key), key)) null ? null : e.value;}//根据键获取值的具体查找过程final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,V first, e; int n; K k;//如果当前哈希表不为空 哈希表中的键值对个数大于0 key所对应位置上的值不为null则继续进行//(n - 1) hash用来获取key的hash值对应数组的下标//n tab.length n-1则一定小于数组的长度并且数组的长度为2的n次幂//与hash值做与运算则可以保证key值对应的hash值和数组的下标有关系并且不大于数组的长度当n16时如下//00000000 00010000 十进制减去1则得到 00000000 00001111 所以与hash做与运算则得到的下标值是根据哈希值得到的并且一定小于16//00000000 00001111//00000010 10110101 //-------------------------//00000000 00000101//这也是为什么数组的大小一定要是2的n次幂的原因if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) {//如果结点first的hash值和key值均相等则可确定key对应的结点就是first直接返回if (first.hash hash ((k first.key) key || (key ! null key.equals(k)))){ return first;} //key不相等如果first结点存在后继结点则继续程序if ((e first.next) ! null) {//如果first是树结点则按着树的规则获取值if (first instanceof TreeNode)return ((TreeNodeK,V)first).getTreeNode(hash, key);//如果first不是树结点则遍历链表的每一个结点key相同时返回对应值do {if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}return null;}//-------------------------------------- 添加方法 ------------------// //添加键值对修改键对应的值public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}//添加的具体操作 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;//先获取到哈希表中数组的长度因为哈希表为空所以先初始化一下if ((tab table) null || (n tab.length) 0){n (tab resize()).length;}//根据hash值获取指定位置上的value如果valuenull说明没有hash冲突则直接添加此结点if ((p tab[i (n - 1) hash]) null){tab[i] newNode(hash, key, value, null);}else {//存在hash冲突NodeK,V e; K k;//key相同则覆盖之前的key所对应的valueif (p.hash hash ((k p.key) key || (key ! null key.equals(k)))){e p;}else if (p instanceof TreeNode){//存在冲突并且已经按着红黑树结构存储则按着红黑树结构添加元素e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);}else {//存在冲突使用链表的方式解决冲突则遍历链表如果存在相同的key则覆盖vlaue不存在则添加到末端for (int binCount 0; ; binCount) {if ((e p.next) null) {p.next newNode(hash, key, value, null);//判断是否需要将链表转成红黑树if (binCount TREEIFY_THRESHOLD - 1) {treeifyBin(tab, hash);} break;}//直接覆盖if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}if (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}modCount;if (size threshold)//如果哈希表中的键值对个数已经达到了阈值则需要扩容resize();afterNodeInsertion(evict);return null;}//初始化哈希表或者对哈希表进行扩容final NodeK,V[] resize() {NodeK,V[] oldTab table;int oldCap (oldTab null) ? 0 : oldTab.length;int oldThr threshold;int newCap, newThr 0;//如果旧的数组长度大于0if (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;} else if (oldThr 0){newCap oldThr;} else {//数组为空初始化数组长度和阈值newCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//如果新的散列的阈值等于0if (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})NodeK,V[] newTab (NodeK,V[])new Node[newCap];//新创建一个数组table newTab;//如果旧的数组中有值则将值按着如下规则复制到新的数组中if (oldTab ! null) {for (int j 0; j oldCap; j) {NodeK,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){//存在冲突已经按着红黑树进行存储((TreeNodeK,V)e).split(this, newTab, j, oldCap);} else { //存在冲突使用链表结构存储//重新散列并不是将链表复制过去NodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;do {next e.next;if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}else {if (hiTail null)hiHead e;elsehiTail.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;}//将链表转换成红黑树final void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,V e;//如果哈希表中的数组为空或者哈希表的大小还未达到需要转换冲红黑树的容量则只是初始化或者扩容if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY){resize();} else if ((e tab[index (n - 1) hash]) ! null) {//链表转成红黑树TreeNodeK,V hd null, tl null;do {TreeNodeK,V p replacementTreeNode(e, null);if (tl null)hd p;else {p.prev tl;tl.next p;}tl p;} while ((e e.next) ! null);if ((tab[index] hd) ! null){hd.treeify(tab);} }}//-------------------------------------- 删除方法 -----------------// //根据key删除键值对public V remove(Object key) {NodeK,V e;return (e removeNode(hash(key), key, null, false, true)) null ? null : e.value;}//删除的具体操作final NodeK,V removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {NodeK,V[] tab; NodeK,V p; int n, index;//如果key的hash码所对应数组下标位置上存在值则继续程序if ((tab table) ! null (n tab.length) 0 (p tab[index (n - 1) hash]) ! null) {NodeK,V node null, e; K k; V v;//如果hash值相同并且key相同则说明没有冲突获取结点if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))){node p;} else if ((e p.next) ! null) {if (p instanceof TreeNode){//存在冲突已经使用红黑树进行存储数据获取结点node ((TreeNodeK,V)p).getTreeNode(hash, key);} else {//链表存储获取结点do {if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) {node e;break;}p e;} while ((e e.next) ! null);}}//如果结点不为空则说明存在key对应的结点则删除if (node ! null (!matchValue || (v node.value) value || (value ! null value.equals(v)))) {if (node instanceof TreeNode)//红黑树删除结点((TreeNodeK,V)node).removeTreeNode(this, tab, movable);else if (node p)//直接删除tab[index] node.next;else//链表删除p.next node.next;modCount;--size;afterNodeRemoval(node);return node;}}return null;}//-------------------------------------- 遍历操作 --------------------// //获取哈希表中所有键值对的keypublic SetK keySet() {SetK ks keySet;if (ks null) {ks new KeySet();keySet ks;}return ks;}final class KeySet extends AbstractSetK {public final int size() { return size; }public final void clear() { HashMap.this.clear(); }public final IteratorK iterator() { return new KeyIterator(); }public final boolean contains(Object o) { return containsKey(o); }public final boolean remove(Object key) {return removeNode(hash(key), key, null, false, true) ! null;}public final SpliteratorK spliterator() {return new KeySpliterator(HashMap.this, 0, -1, 0, 0);}public final void forEach(Consumer? super K action) {NodeK,V[] tab;if (action null)throw new NullPointerException();if (size 0 (tab table) ! null) {int mc modCount;for (int i 0; i tab.length; i) {for (NodeK,V e tab[i]; e ! null; e e.next)action.accept(e.key);}if (modCount ! mc)throw new ConcurrentModificationException();}}}//获取hash表中所有的valuepublic CollectionV values() {CollectionV vs values;if (vs null) {vs new Values();values vs;}return vs;}final class Values extends AbstractCollectionV {public final int size() { return size; }public final void clear() { HashMap.this.clear(); }public final IteratorV iterator() { return new ValueIterator(); }public final boolean contains(Object o) { return containsValue(o); }public final SpliteratorV spliterator() {return new ValueSpliterator(HashMap.this, 0, -1, 0, 0);}public final void forEach(Consumer? super V action) {NodeK,V[] tab;if (action null)throw new NullPointerException();if (size 0 (tab table) ! null) {int mc modCount;for (int i 0; i tab.length; i) {for (NodeK,V e tab[i]; e ! null; e e.next)action.accept(e.value);}if (modCount ! mc)throw new ConcurrentModificationException();}}}//将hash表中所有的键值键值对放到一个set集合中public SetMap.EntryK,V entrySet() {SetMap.EntryK,V es;return (es entrySet) null ? (entrySet new EntrySet()) : es;}final class EntrySet extends AbstractSetMap.EntryK,V {public final int size() { return size; }public final void clear() { HashMap.this.clear(); }public final IteratorMap.EntryK,V iterator() {return new EntryIterator();}public final boolean contains(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry?,? e (Map.Entry?,?) o;Object key e.getKey();NodeK,V candidate getNode(hash(key), key);return candidate ! null candidate.equals(e);}public final boolean remove(Object o) {if (o instanceof Map.Entry) {Map.Entry?,? e (Map.Entry?,?) o;Object key e.getKey();Object value e.getValue();return removeNode(hash(key), key, value, true, true) ! null;}return false;}public final SpliteratorMap.EntryK,V spliterator() {return new EntrySpliterator(HashMap.this, 0, -1, 0, 0);}public final void forEach(Consumer? super Map.EntryK,V action) {NodeK,V[] tab;if (action null)throw new NullPointerException();if (size 0 (tab table) ! null) {int mc modCount;for (int i 0; i tab.length; i) {for (NodeK,V e tab[i]; e ! null; e e.next)action.accept(e);}if (modCount ! mc)throw new ConcurrentModificationException();}}}//-------------------------------------- 克隆操作 -------------------// SuppressWarnings(unchecked)Overridepublic Object clone() {HashMapK,V result;try {result (HashMapK,V)super.clone();} catch (CloneNotSupportedException e) {throw new InternalError(e);}result.reinitialize();result.putMapEntries(this, false);return result;}//-------------------------------------- 序列化操作 -----------------////序列化private void writeObject(java.io.ObjectOutputStream s)throws IOException {//删除具体代码}//反序列化private void readObject(java.io.ObjectInputStream s)throws IOException, ClassNotFoundException {//删除具体代码}//hashmap中维护一个红黑树结点静态内部类里边有着一系列处理红黑树的方法static final class TreeNodeK,V extends LinkedHashMap.EntryK,V {TreeNodeK,V parent; TreeNodeK,V left;TreeNodeK,V right;TreeNodeK,V prev; boolean red;TreeNode(int hash, K key, V val, NodeK,V next) {super(hash, key, val, next);}}} 再说一下Hashtable它的实现和HashMap基本相同但是在功能上也存在几点不同分析如下 //继承了Dictionary
public class HashtableK,V extends DictionaryK,V implements MapK,V, Cloneable, java.io.Serializable {//private transient Entry?,?[] table;//键值对个数private transient int count;//阈值private int threshold;//加载因子private float loadFactor;//修改次数private transient int modCount 0;private static final int MAX_ARRAY_SIZE Integer.MAX_VALUE - 8;//-------------------------------构造方法 ------------------------------// public Hashtable(int initialCapacity, float loadFactor) {if (initialCapacity 0)throw new IllegalArgumentException(Illegal Capacity: initialCapacity);if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal Load: loadFactor);if (initialCapacity0)initialCapacity 1;this.loadFactor loadFactor;table new Entry?,?[initialCapacity];threshold (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE 1);}public Hashtable(int initialCapacity) {this(initialCapacity, 0.75f);}public Hashtable() {this(11, 0.75f);}//-------------------------------功能方法 ------------------------------// //返回Enumeration集合,HashMap中是没有的public synchronized EnumerationK keys() {return this.KgetEnumeration(KEYS);}//HashMap中没有这个方法public synchronized boolean contains(Object value) {if (value null) {throw new NullPointerException();}Entry?,? tab[] table;for (int i tab.length ; i-- 0 ;) {for (Entry?,? e tab[i] ; e ! null ; e e.next) {if (e.value.equals(value)) {return true;}}}return false;}//-------------------------------获取方法 ------------------------------// //synchronized修饰方法实线程同步的public synchronized V get(Object key) {Entry?,? tab[] table;//获取下标的方式不同直接使用hash值进行下标获取int hash key.hashCode();int index (hash 0x7FFFFFFF) % tab.length;for (Entry?,? e tab[index] ; e ! null ; e e.next) {if ((e.hash hash) e.key.equals(key)) {return (V)e.value;}}return null;}//-------------------------------添加方法 ------------------------------// public synchronized V put(K key, V value) {//value不可以为空HashMap中就可以if (value null) {throw new NullPointerException();}//判断是否已经存在此key对应的键值对//如果存在则替换Entry?,? tab[] table;int hash key.hashCode();int index (hash 0x7FFFFFFF) % tab.length;SuppressWarnings(unchecked)EntryK,V entry (EntryK,V)tab[index];for(; entry ! null ; entry entry.next) {if ((entry.hash hash) entry.key.equals(key)) {V old entry.value;entry.value value;return old;}}//不存在则添加addEntry(hash, key, value, index);return null;}//具体添加方法private void addEntry(int hash, K key, V value, int index) {modCount;Entry?,? tab[] table;if (count threshold) {//如果哈希表中的键值对数量大于阈值则扩容rehash();tab table;hash key.hashCode();index (hash 0x7FFFFFFF) % tab.length;}//添加SuppressWarnings(unchecked)EntryK,V e (EntryK,V) tab[index];tab[index] new Entry(hash, key, value, e);count;}//扩容操作SuppressWarnings(unchecked)protected void rehash() {int oldCapacity table.length;Entry?,?[] oldMap table;// 扩容成一倍1HashMap是一倍int newCapacity (oldCapacity 1) 1;if (newCapacity - MAX_ARRAY_SIZE 0) {if (oldCapacity MAX_ARRAY_SIZE)return;newCapacity MAX_ARRAY_SIZE;}Entry?,?[] newMap new Entry?,?[newCapacity];modCount;threshold (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE 1);table newMap;for (int i oldCapacity ; i-- 0 ;) {for (EntryK,V old (EntryK,V)oldMap[i] ; old ! null ; ) {EntryK,V e old;old old.next;int index (e.hash 0x7FFFFFFF) % newCapacity;e.next (EntryK,V)newMap[index];newMap[index] e;}}}//Hashtable中不会牵扯到红黑树的操作
}说一下TreeMap它依赖于红黑树实现添加的元素是可以按着关键字排序的排序规则可以自定义分析如下 public interface SortedMapK,V extends MapK,V {}public interface NavigableMapK,V extends SortedMapK,V {}//基于红黑树的实现
//红黑树是一种大致平衡的平衡二叉树根节点和叶子节点是黑色其他节点是黑色或者红色
//每个红色节点的两个子节点是黑色从每个叶子到根的所有路径上不能有两个连续的红色节点
//从任意一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点
public class TreeMapK,V extends AbstractMapK,V implements NavigableMapK,V, Cloneable, java.io.Serializable
{//比较器用于维护树中元素的顺序private final Comparator? super K comparator;//树private transient EntryK,V root;//节点个数private transient int size 0;//修改次数private transient int modCount 0;//------------------------------构造函数--------------------// public TreeMap() {comparator null;}//自定义构造器初始化TreeMappublic TreeMap(Comparator? super K comparator) {this.comparator comparator;}//根据现有的TreeMap构建一个TreeMap实例public TreeMap(SortedMapK, ? extends V m) {comparator m.comparator();try {buildFromSorted(m.size(), m.entrySet().iterator(), null, null);} catch (java.io.IOException cannotHappen) {} catch (ClassNotFoundException cannotHappen) {}}//树中所含元素个数public int size() {return size;}//------------------------------ 添加元素 --------------------// //添加元素public V put(K key, V value) {EntryK,V t root;//初始化根节点if (t null) {compare(key, key); root new Entry(key, value, null);size 1;modCount;return null;}//如果已经有数据了int cmp;EntryK,V parent;//获取到比较器Comparator? super K cpr comparator;if (cpr ! null) {//如果比较器不为空按着比较器规则比较do {parent t;cmp cpr.compare(key, t.key);if (cmp 0)//如果cmp0继续比较左子树t t.left;else if (cmp 0)//如果cmp0继续比较右子树t t.right;elsereturn t.setValue(value);//值相同直接覆盖} while (t ! null);} else {//没有比较器默认比较器比较if (key null)throw new NullPointerException();SuppressWarnings(unchecked)Comparable? super K k (Comparable? super K) key;do {parent t;cmp k.compareTo(t.key);if (cmp 0)t t.left;else if (cmp 0)t t.right;elsereturn t.setValue(value);} while (t ! null);}//添加节点EntryK,V e new Entry(key, value, parent);if (cmp 0)parent.left e;elseparent.right e;fixAfterInsertion(e);size;modCount;return null;}//------------------------------ 获取元素 --------------------////根据key获取valuepublic V get(Object key) {EntryK,V p getEntry(key);return (pnull ? null : p.value);}//获取值的具体操作final EntryK,V getEntry(Object key) {if (comparator ! null)return getEntryUsingComparator(key);if (key null)throw new NullPointerException();//根据默认的比较器查找对应key的value值Comparable? super K k (Comparable? super K) key;EntryK,V p root;while (p ! null) {int cmp k.compareTo(p.key);if (cmp 0)p p.left;else if (cmp 0)p p.right;elsereturn p;}return null;}//根据自定义比较器查找key对应的value值final EntryK,V getEntryUsingComparator(Object key) {K k (K) key;Comparator? super K cpr comparator;if (cpr ! null) {EntryK,V p root;while (p ! null) {int cmp cpr.compare(k, p.key);if (cmp 0)p p.left;else if (cmp 0)p p.right;elsereturn p;}}return null;}//------------------------------ 移除元素 --------------------////根据key获取到节点然后返回对应值删除节点public V remove(Object key) {EntryK,V p getEntry(key);if (p null)return null;V oldValue p.value;deleteEntry(p);return oldValue;}//删除的具体操作private void deleteEntry(EntryK,V p) {modCount;size--;//如果被删除的节点有左右子结点if (p.left ! null p.right ! null) {EntryK,V s successor(p);p.key s.key;p.value s.value;p s;}EntryK,V replacement (p.left ! null ? p.left : p.right);if (replacement ! null) {replacement.parent p.parent;if (p.parent null)root replacement;else if (p p.parent.left)p.parent.left replacement;elsep.parent.right replacement;p.left p.right p.parent null;if (p.color BLACK)fixAfterDeletion(replacement);} else if (p.parent null) { //删除唯一的节点root null;} else { // 删除的节点没有子节点直接删除即可if (p.color BLACK)fixAfterDeletion(p);if (p.parent ! null) {if (p p.parent.left)p.parent.left null;else if (p p.parent.right)p.parent.right null;p.parent null;}}}//删除一个节点依次移动节点以保证平衡static K,V TreeMap.EntryK,V successor(EntryK,V t) {if (t null)return null;else if (t.right ! null) {EntryK,V p t.right;while (p.left ! null)p p.left;return p;} else {EntryK,V p t.parent;EntryK,V ch t;while (p ! null ch p.right) {ch p;p p.parent;}return p;}}//还有一些其他的不同于HahhMap的方法在这里不做介绍
}最后说一下LinkedHashMap它继承自HashMap它将集合中的元素使用一个双向链表进行连接在存取上是有序的LinkedHashMap可以看成是使用HashMap进行存储元素链表链接元素保证顺序分析如下
public class LinkedHashMapK,V extends HashMapK,V implements MapK,V
{//每一个结点添加before、after属性用来记录存取顺序static class EntryK,V extends HashMap.NodeK,V {EntryK,V before, after;Entry(int hash, K key, V value, NodeK,V next) {super(hash, key, value, next);}}//双向链表的头结点transient LinkedHashMap.EntryK,V head;//双向链表的尾节点transient LinkedHashMap.EntryK,V tail;//以什么顺序进行链接//accessOrder为true时按访问顺序//accessOrder为false时按插入顺序默认final boolean accessOrder;//---------------------------构造函数----------------------////使用父类构造方法public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder false;//默认按插入顺序}public LinkedHashMap(int initialCapacity) {super(initialCapacity);accessOrder false;//}public LinkedHashMap() {super();accessOrder false;}public LinkedHashMap(Map? extends K, ? extends V m) {super();accessOrder false;putMapEntries(m, false);}//---------------------------功能函数----------------------////---------------------------添加方法----------------------////用的时HashMap中的put方法public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}//具体添加onlyIfAbsentevict这两个参数发挥作用final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;if ((tab table) null || (n tab.length) 0)n (tab resize()).length;if ((p tab[i (n - 1) hash]) null)tab[i] newNode (hash, key, value, null);else {NodeK,V e; K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount 0; ; binCount) {if ((e p.next) null) {p.next newNode(hash, key, value, null);if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}if (e ! null) {V oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);//按访问顺序return oldValue;}}modCount;if (size threshold)resize();afterNodeInsertion(evict);return null;}//按访问顺序链接将结点链接到最后void afterNodeAccess(NodeK,V e) {LinkedHashMap.EntryK,V last;if (accessOrder (last tail) ! e) {LinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,V)e, b p.before, a p.after;p.after null;if (b null)head a;elseb.after a;if (a ! null)a.before b;elselast b;if (last null)head p;else {p.before last;last.after p;}tail p;modCount;}}//LinkedHashMap就是用一个双向链表将HashMap中的元素链接起来保证有序这里只说一个保持顺序的方法
}
以上是对Map集合做一下简单介绍。
