260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

 

解题思路：

题目要求给定数组，数组中有且只有两个元素只出现一次，其他元素都重复出现2次，返回只出现一次的元素。

首先遍历数组，使用异或操作得到一个数tmp，由于有两个元素只出现一次，因此异或出来的结果一定不为0。而这两个只出现一次的元素进行异或一定不为0，即至少有1个位一个元素为0，另一个元素为1。tmp的二进制中为1的位置即可区分两个元素，从tmp中提取出一个1得到的数作为掩码，遍历数组，与掩码进行与操作，若为0，则与元素1异或，否则与元素2异或，这样即可将两个只出现一次的元素分开，同时，重复出现的元素会被分到同一类中，当进行异或时，对结果无影响。

影响运行效率的地方：

从tmp中提取出一个1的方法：

1、首先使用tmp&(tmp-1)得到tmp去掉最低位1的数，再与tmp异或即得到该数(tmp&(tmp-1)^tmp，tmp^(tmp&(tmp-1))，这两个书写方式不同，运行所花费的时间也不同，前者相比于后者快些)

2、tmp&(~(tmp-1))也是取最后一个1的，运行所花费的时间与tmp^(tmp&(tmp-1)相同。

class Solution { public:     vector<int> singleNumber(vector<int>& nums) {     int n=nums.size();     if(n==2)return nums;     vector<int>res=vector<int>(2,0);     int a=0,b=0;     int tmp=0;     for(int i=0;i<n;i++){         tmp^=nums[i];     }     // 20ms     //tmp&=(~(tmp-1));     // 20ms     tmp=tmp^(tmp&(tmp-1));     // 18ms     // tmp=tmp&(tmp-1)^tmp;     for(int i=0;i<n;i++){         if(nums[i]&tmp)res[0]^=nums[i];         else             res[1]^=nums[i];     }     return res;     } };

保存中间变量所使用的变量类型：

1、在开始时就新建vector对象，中间变量保存到vector数组中

class Solution { public:     vector<int> singleNumber(vector<int>& nums) {     int n=nums.size();     if(n==2)return nums;     // 18ms     vector<int>res=vector<int>(2,0);     int tmp=0;     for(int i=0;i<n;i++){         tmp^=nums[i];     }     tmp=tmp&(tmp-1)^tmp     for(int i=0;i<n;i++){         if(nums[i]&tmp)res[0]^=nums[i];         else             res[1]^=nums[i];     }     return res;     } };

2、先使用int类型保存中间变量，最后使用vector<int>{a,b}的方式保存最后结果，该方法比1要快写。

class Solution { public:     vector<int> singleNumber(vector<int>& nums) {     int n=nums.size();     if(n==2)return nums;     // 16ms     int a=0,b=0;     int tmp=0;     for(int i=0;i<n;i++){         tmp^=nums[i];     }     tmp=tmp&(tmp-1)^tmp     for(int i=0;i<n;i++){         if(nums[i]&tmp)a^=nums[i];         else             b^=nums[i];     }     return vector<int>{a,b};     } };

 

Map之HashMap源码分析

 

public class HashMap<K,V>     extends AbstractMap<K,V>     implements Map<K,V>, Cloneable, Serializable

HashMap继承自AbstractMap，实现了Map接口，有map的基本操作；实现了Cloneable接口，使得该类是可克隆的；实现了Serializable接口，说明该类支持序列化。HashMap是线程不安全的。源码版本为JDK1.7.0_75

 

HashMap的数据结构

紫色的对应Entry<K,V>[] table，绿色的是Entry<K,V>对象队列，解决hash冲突。

在put时，首先调用hashCode方法获得哈希值，在调用indexFor方法获取该key存放在table数组的下标index，新建entry插入到index所指向的链表的队首。在删除时也是通过相同的方法找到该key所在的index，然后遍历链表，将key相同、hash值相等的entry删除。

HashMap还对map存放的key-value数目进行限制（使用threshold），且要求数组大小（capacity）必须是2的幂次方（考虑indexFor方法），当容量无法将entry全部保存或者entry数目超过threshold时，根据loadfactor使用resize对容量进行扩大，其中threshold=capacity*loadfactor。

HashMap中允许存放key为null的entry，对于key为null，其index为0。

inflateTable方法是在当table==EMPTY_TABLE时才用到,用于初始化table。

 

成员变量

/** * 默认初始化空间——必须为2的倍数      * The default initial capacity - MUST be a power of two.      */     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16       /** * 最大空间，若在构造方法中没有给定，则使用该值——必须为2的倍数      * The maximum capacity, used if a higher value is implicitly specified      * by either of the constructors with arguments.      * MUST be a power of two <= 1<<30.      */     static final int MAXIMUM_CAPACITY = 1 << 30;       /** * 若在构造时没有指出则使用该值作为加载因子      * The load factor used when none specified in constructor.      */     static final float DEFAULT_LOAD_FACTOR = 0.75f;       /** * 当表格没有膨胀，则空表实例      * An empty table instance to share when the table is not inflated.      */     static final Entry<?,?>[] EMPTY_TABLE = {};       /** * 哈希表，有必要时需resize。长度总是2的倍数      * The table, resized as necessary. Length MUST Always be a power of two.      */     transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;       /** * map中包含的key-value映射数目      * The number of key-value mappings contained in this map.      */     transient int size;       /** * 调整大小的值？？ 临界值，当实际大小超过临界值时，会进行resize,threshold=capacity*load factor      * The next size value at which to resize (capacity * load factor).      * @serial      */     // If table == EMPTY_TABLE then this is the initial capacity at which the     // table will be created when inflated.     int threshold;       /** * 哈希表的加载因子      * The load factor for the hash table.      *      * @serial      */     final float loadFactor;       /** * HashMap进行结构上修改的次数。用来是对HashMap的集合上的迭代器fast-fail      * The number of times this HashMap has been structurally modified      * Structural modifications are those that change the number of mappings in      * the HashMap or otherwise modify its internal structure (e.g.,      * rehash).  This field is used to make iterators on Collection-views of      * the HashMap fail-fast.  (See ConcurrentModificationException).      */     transient int modCount;       /** * 当使用string作为键值的哈希时的map容量的默认阈值。。。      * The default threshold of map capacity above which alternative hashing is      * used for String keys. Alternative hashing reduces the incidence of      * collisions due to weak hash code calculation for String keys.      * <p/>      * This value may be overridden by defining the system property      * {@code jdk.map.althashing.threshold}. A property value of {@code 1}      * forces alternative hashing to be used at all times whereas      * {@code -1} value ensures that alternative hashing is never used.      */     static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;     /** * 随机值，用在keys的hash code上，使得哈希冲突较难发生。若该值为0，则alternative hash不可用（我理解的是二次哈希）      * A randomizing value associated with this instance that is applied to      * hash code of keys to make hash collisions harder to find. If 0 then      * alternative hashing is disabled.      */     transient int hashSeed = 0;

loadFactor为加载因子，表示hash表中元素的填满程度，加载因子越大，空间利用率高，但冲突机会就加大了，链表长度会越来越长，查找效率将降低；反之，加载因子越小，填满的元素越少，冲突机会减少，但空间浪费了。

冲突机会越大，则查找效率将降低。

因此，需要在"冲突机会"与"空间利用率"之间寻找平衡——类似"时空"平衡。

参考：

http://www.cnblogs.com/ITtangtang/p/3948406.html

 

私有静态内部类Holder

/** * 保存那些直到虚拟机启动时才能初始化的值      * holds values which can't be initialized until after VM is booted.      */     private static class Holder {           /**     * 当转向使用alternative hashing时，table的容量          * Table capacity above which to switch to use alternative hashing.          */         static final int ALTERNATIVE_HASHING_THRESHOLD;           static {             String altThreshold = java.security.AccessController.doPrivileged(                 new sun.security.action.GetPropertyAction(                     "jdk.map.althashing.threshold"));               int threshold;             try {                 threshold = (null != altThreshold)                         ? Integer.parseInt(altThreshold)                         : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;                   // disable alternative hashing if -1                 if (threshold == -1) {                     threshold = Integer.MAX_VALUE;                 }                   if (threshold < 0) {                     throw new IllegalArgumentException("value must be positive integer.");                 }             } catch(IllegalArgumentException failed) {                 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);             }               ALTERNATIVE_HASHING_THRESHOLD = threshold;         }     }

 

构造函数

/** * 指定了初始容量和加载因子，构造一个空HashMap      * Constructs an empty <tt>HashMap</tt> with the specified initial      * capacity and load factor.      *      * @param  initialCapacity the initial capacity      * @param  loadFactor      the load factor      * @throws IllegalArgumentException if the initial capacity is negative      *         or the load factor is nonpositive      */     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;         threshold = initialCapacity;         init();     }       /**      * Constructs an empty <tt>HashMap</tt> with the specified initial      * capacity and the default load factor (0.75).      *      * @param  initialCapacity the initial capacity.      * @throws IllegalArgumentException if the initial capacity is negative.      */     public HashMap(int initialCapacity) {         this(initialCapacity, DEFAULT_LOAD_FACTOR);     }       /**      * Constructs an empty <tt>HashMap</tt> with the default initial capacity      * (16) and the default load factor (0.75).      */     public HashMap() {         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);     }       /**      * Constructs a new <tt>HashMap</tt> with the same mappings as the      * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with      * default load factor (0.75) and an initial capacity sufficient to      * hold the mappings in the specified <tt>Map</tt>.      *      * @param   m the map whose mappings are to be placed in this map      * @throws  NullPointerException if the specified map is null      */     public HashMap(Map<? extends K, ? extends V> m) {         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,                       DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);         inflateTable(threshold);           putAllForCreate(m);     }

 

inflateTable，该方法在table==EMPTY_TABLE时被调用，用于初始化table，并将capacity提至2的幂次方。

private static int roundUpToPowerOf2(int number) {         // assert number >= 0 : "number must be non-negative";         return number >= MAXIMUM_CAPACITY                 ? MAXIMUM_CAPACITY                 : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;     }    /**      * Inflates the table.      */     private void inflateTable(int toSize) {         // Find a power of 2 >= toSize         int capacity = roundUpToPowerOf2(toSize);           threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);         table = new Entry[capacity];         initHashSeedAsNeeded(capacity);     }       // internal utilities       /** * 为子类初始化hook（钩子）。该方法在构造方法和伪构造方法（clone，readObject）中初始化HashMap之后entry被插入之前调用的。没有该方法，readObject将需要子类信息。      * Initialization hook for subclasses. This method is called      * in all constructors and pseudo-constructors (clone, readObject)      * after HashMap has been initialized but before any entries have      * been inserted.  (In the absence of this method, readObject would      * require explicit knowledge of subclasses.)      */     void init() {     }       /** * 初始化哈希mask值。直到真的需要用到hashseed时，才初始化它。      * Initialize the hashing mask value. We defer initialization until we      * really need it.      */     final boolean initHashSeedAsNeeded(int capacity) {         boolean currentAltHashing = hashSeed != 0;         boolean useAltHashing = sun.misc.VM.isBooted() &&                 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);         boolean switching = currentAltHashing ^ useAltHashing;         if (switching) {             hashSeed = useAltHashing                 ? sun.misc.Hashing.randomHashSeed(this)                 : 0;         }         return switching;     }

 

hashing相关

/** * 获得对象哈希码，并将一个补充的哈希函数应用到哈希结果以防poor哈希函数。 *  注意：键为null总是映射到哈希0，因此索引为0。      * Retrieve object hash code and applies a supplemental hash function to the      * result hash, which defends against poor quality hash functions.  This is      * critical because HashMap uses power-of-two length hash tables, that      * otherwise encounter collisions for hashCodes that do not differ      * in lower bits. Note: Null keys always map to hash 0, thus index 0.      */     final int hash(Object k) {         int h = hashSeed;         if (0 != h && k instanceof String) {             return sun.misc.Hashing.stringHash32((String) k);         }           h ^= k.hashCode();         // 通过若干次移位、异或操作，把hashCode的1的位置变得"松散，均匀"，                     //  以免在计算index时不均匀                     //  等价于操作 h ^ (h >>> 4) ^ (h >>> 7) ^ (h >>> 12) ^ (h >>> 16) ^ (h >>> 20) ^ (h >>> 24) ^ (h >>> 27);                      // 将hashcode用十六进制表示为…nmlkjihgfedcba，则a'=a^b^c…,b'=b^c^d…,c'=c^d^e…         // This function ensures that hashCodes that differ only by         // constant multiples at each bit position have a bounded         // number of collisions (approximately 8 at default load factor).         h ^= (h >>> 20) ^ (h >>> 12);         return h ^ (h >>> 7) ^ (h >>> 4);     }       /** * 返回哈希码h的索引 *   因为length为2的幂次方，因此length-1使用二进制表示所有位都是1，即111111..，h&(length-1)得到的数可以均匀分布到table数组上，例如length=8，则1&7=1,2&7=2,3&7=3,…7&7=7,8&7=0,9&7=1..，可以看出该公式相当于h%length，注意的是针对length要为2的幂次方。      * Returns index for hash code h.      */     static int indexFor(int h, int length) {         // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";         return h & (length-1);     }

 

Get key相关

/** * 返回给定key在map上对应的value，若map中没有该key，则返回null。      * Returns the value to which the specified key is mapped,      * or {@code null} if this map contains no mapping for the key.      *      * <p>More formally, if this map contains a mapping from a key      * {@code k} to a value {@code v} such that {@code (key==null ? k==null :     * key.equals(k))}, then this method returns {@code v}; otherwise      * it returns {@code null}.  (There can be at most one such mapping.)      *      * <p>A return value of {@code null} does not <i>necessarily</i>      * indicate that the map contains no mapping for the key; it's also      * possible that the map explicitly maps the key to {@code null}.      * The {@link #containsKey containsKey} operation may be used to      * distinguish these two cases.      *      * @see #put(Object, Object)      */     public V get(Object key) {         if (key == null)             return getForNullKey();         Entry<K,V> entry = getEntry(key);           return null == entry ? null : entry.getValue();     }       /** * 获取key为null所对应的value。前面提到key为null对应的索引为0，因此从table[0] *  开始遍历。      * Offloaded version of get() to look up null keys.  Null keys map      * to index 0.  This null case is split out into separate methods      * for the sake of performance in the two most commonly used      * operations (get and put), but incorporated with conditionals in      * others.      */     private V getForNullKey() {         if (size == 0) {             return null;         }         for (Entry<K,V> e = table[0]; e != null; e = e.next) {             if (e.key == null)                 return e.value;         }         return null;     }       /**      * Returns <tt>true</tt> if this map contains a mapping for the      * specified key.      *      * @param   key   The key whose presence in this map is to be tested      * @return <tt>true</tt> if this map contains a mapping for the specified      * key.      */     public boolean containsKey(Object key) {         return getEntry(key) != null;     }       /**      * Returns the entry associated with the specified key in the      * HashMap.  Returns null if the HashMap contains no mapping      * for the key.      */     final Entry<K,V> getEntry(Object key) {         if (size == 0) {             return null;         }           int hash = (key == null) ? 0 : hash(key);         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;     }

 

Put 相关

/** * 根据key值将key-value对插入到map中，若key已存在，则更新value。返回插入前map * 中key所对应的value值。      * Associates the specified value with the specified key in this map.      * If the map previously contained a mapping for the key, the old      * value is replaced.      *      * @param key key with which the specified value is to be associated      * @param value value to be associated with the specified key      * @return the previous value associated with <tt>key</tt>, or      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.      *         (A <tt>null</tt> return can also indicate that the map      *         previously associated <tt>null</tt> with <tt>key</tt>.)      */     public V put(K key, V value) {         if (table == EMPTY_TABLE) {             inflateTable(threshold);         }         if (key == null)             return putForNullKey(value);         int hash = hash(key);         int i = indexFor(hash, table.length);         for (Entry<K,V> e = table[i]; e != null; e = e.next) {             Object k;             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {                 V oldValue = e.value;                 e.value = value;                 e.recordAccess(this);                 return oldValue;             }         }           modCount++;         addEntry(hash, key, value, i);         return null;     }       /** * 设置key为null时的value值。      * Offloaded version of put for null keys      */     private V putForNullKey(V value) {         for (Entry<K,V> e = table[0]; e != null; e = e.next) {             if (e.key == null) {                 V oldValue = e.value;                 e.value = value;                 e.recordAccess(this);                 return oldValue;             }         }         modCount++;         addEntry(0, null, value, 0);         return null;     }       /** * 不同于put，该方法不需要resize table，构造方法或伪构造方法(clone，readObject)调用该方法。      * This method is used instead of put by constructors and      * pseudoconstructors (clone, readObject).  It does not resize the table,      * check for comodification, etc.  It calls createEntry rather than      * addEntry.      */     private void putForCreate(K key, V value) {         int hash = null == key ? 0 : hash(key);         int i = indexFor(hash, table.length);           /**          * Look for preexisting entry for key.  This will never happen for          * clone or deserialize.  It will only happen for construction if the          * input Map is a sorted map whose ordering is inconsistent w/ equals.          */         for (Entry<K,V> e = table[i]; e != null; e = e.next) {             Object k;             if (e.hash == hash &&                 ((k = e.key) == key || (key != null && key.equals(k)))) {                 e.value = value;                 return;             }         }           createEntry(hash, key, value, i);     }       private void putAllForCreate(Map<? extends K, ? extends V> m) {         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())             putForCreate(e.getKey(), e.getValue());     }

 

Resize

/** * 将原来map内容重哈希到一个更大容量的新数组上。当map中key数目达到threshold时，自动调用该方法。若当前容量为MAXIMUM_CAPACITY，则不resize map，设置threshold为Integer.MAX_VALUE。      * Rehashes the contents of this map into a new array with a      * larger capacity.  This method is called automatically when the      * number of keys in this map reaches its threshold.      *      * If current capacity is MAXIMUM_CAPACITY, this method does not      * resize the map, but sets threshold to Integer.MAX_VALUE.      * This has the effect of preventing future calls.      *      * @param newCapacity the new capacity, MUST be a power of two;      *        must be greater than current capacity unless current      *        capacity is MAXIMUM_CAPACITY (in which case value      *        is irrelevant).      */     void resize(int newCapacity) {         Entry[] oldTable = table;         int oldCapacity = oldTable.length;         if (oldCapacity == MAXIMUM_CAPACITY) {             threshold = Integer.MAX_VALUE;             return;         }           Entry[] newTable = new Entry[newCapacity];         transfer(newTable, initHashSeedAsNeeded(newCapacity));         table = newTable;         threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);     }       /** * 将当前表中所有entry转换到newTable中。rehash标志转换时是否需要重哈希。      * Transfers all entries from current table to newTable.      */     void transfer(Entry[] newTable, boolean rehash) {         int newCapacity = newTable.length;         for (Entry<K,V> e : table) {             while(null != e) {                 Entry<K,V> next = e.next;                 if (rehash) {                     e.hash = null == e.key ? 0 : hash(e.key);                 }                 int i = indexFor(e.hash, newCapacity);                 e.next = newTable[i];                 newTable[i] = e;                 e = next;             }         }     }

 

将m中的key-value对全都复制到map中，在put之前，首先对table进行resize，若要添加的键-值对大于threshold，则对table进行resize。

/**      * Copies all of the mappings from the specified map to this map.      * These mappings will replace any mappings that this map had for      * any of the keys currently in the specified map.      *      * @param m mappings to be stored in this map      * @throws NullPointerException if the specified map is null      */     public void putAll(Map<? extends K, ? extends V> m) {         int numKeysToBeAdded = m.size();         if (numKeysToBeAdded == 0)             return;           if (table == EMPTY_TABLE) {             inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));         }           /*          * Expand the map if the map if the number of mappings to be added          * is greater than or equal to threshold.  This is conservative; the          * obvious condition is (m.size() + size) >= threshold, but this          * condition could result in a map with twice the appropriate capacity,          * if the keys to be added overlap with the keys already in this map.          * By using the conservative calculation, we subject ourself          * to at most one extra resize.          */         if (numKeysToBeAdded > threshold) {             int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);             if (targetCapacity > MAXIMUM_CAPACITY)                 targetCapacity = MAXIMUM_CAPACITY;             int newCapacity = table.length;             while (newCapacity < targetCapacity)                 newCapacity <<= 1;             if (newCapacity > table.length)                 resize(newCapacity);         }           for (Map.Entry<? extends K, ? extends V> e : m.entrySet())             put(e.getKey(), e.getValue());     }

 

删除。。。删除特定key，首先根据key，计算hash，得到索引，获取所在的"桶"，遍历桶内的链表，删除hash相等且key相等的entry。

/**      * Removes the mapping for the specified key from this map if present.      *      * @param  key key whose mapping is to be removed from the map      * @return the previous value associated with <tt>key</tt>, or      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.      *         (A <tt>null</tt> return can also indicate that the map      *         previously associated <tt>null</tt> with <tt>key</tt>.)      */     public V remove(Object key) {         Entry<K,V> e = removeEntryForKey(key);         return (e == null ? null : e.value);     }       /** * 删除并返回key所对应的entry，若map中不存在该key，返回null。      * Removes and returns the entry associated with the specified key      * in the HashMap.  Returns null if the HashMap contains no mapping      * for this key.      */     final Entry<K,V> removeEntryForKey(Object key) {         if (size == 0) {             return null;         }         int hash = (key == null) ? 0 : hash(key);         int i = indexFor(hash, table.length);         Entry<K,V> prev = table[i];         Entry<K,V> e = prev;           while (e != null) {             Entry<K,V> next = e.next;             Object k;             if (e.hash == hash &&                 ((k = e.key) == key || (key != null && key.equals(k)))) {                 modCount++;                 size--;                 if (prev == e)                     table[i] = next;                 else                     prev.next = next;                 e.recordRemoval(this);                 return e;             }             prev = e;             e = next;         }           return e;     }         /** * 根据Map.Entry.equals方法找出与对象o相匹配的entry，将其删除。      * Special version of remove for EntrySet using {@code Map.Entry.equals()}      * for matching.      */     final Entry<K,V> removeMapping(Object o) {         if (size == 0 || !(o instanceof Map.Entry))             return null;           Map.Entry<K,V> entry = (Map.Entry<K,V>) o;         Object key = entry.getKey();         int hash = (key == null) ? 0 : hash(key);         int i = indexFor(hash, table.length);         Entry<K,V> prev = table[i];         Entry<K,V> e = prev;           while (e != null) {             Entry<K,V> next = e.next;             if (e.hash == hash && e.equals(entry)) {                 modCount++;                 size--;                 if (prev == e)                     table[i] = next;                 else                     prev.next = next;                 e.recordRemoval(this);                 return e;             }             prev = e;             e = next;         }           return e;     }

 

/** * 删除map中所有映射，使用Arrays.fill方法将table数组的值都设为null      * Removes all of the mappings from this map.      * The map will be empty after this call returns.      */     public void clear() {         modCount++;         Arrays.fill(table, null);         size = 0;     }

 

containXXX类方法

/**      * Returns <tt>true</tt> if this map maps one or more keys to the      * specified value.      *      * @param value value whose presence in this map is to be tested      * @return <tt>true</tt> if this map maps one or more keys to the      *         specified value      */     public boolean containsValue(Object value) {         if (value == null)             return containsNullValue();           Entry[] tab = table;         for (int i = 0; i < tab.length ; i++)             for (Entry e = tab[i] ; e != null ; e = e.next)                 if (value.equals(e.value))                     return true;         return false;     }       /**      * Special-case code for containsValue with null argument      */     private boolean containsNullValue() {         Entry[] tab = table;         for (int i = 0; i < tab.length ; i++)             for (Entry e = tab[i] ; e != null ; e = e.next)                 if (e.value == null)                    return true;         return false;     }

 

clone方法

/**      * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and      * values themselves are not cloned.      *      * @return a shallow copy of this map      */     public Object clone() {         HashMap<K,V> result = null;         try {             result = (HashMap<K,V>)super.clone();         } catch (CloneNotSupportedException e) {             // assert false;         }         if (result.table != EMPTY_TABLE) {             result.inflateTable(Math.min(                 (int) Math.min(                     size * Math.min(1 / loadFactor, 4.0f),                     // we have limits...                     HashMap.MAXIMUM_CAPACITY),                table.length));         }         result.entrySet = null;         result.modCount = 0;         result.size = 0;         result.init();         result.putAllForCreate(this);           return result;     }

 

静态内部类Entry

static class Entry<K,V> implements Map.Entry<K,V> {         final K key;         V value;         Entry<K,V> next;         int hash;           /**          * Creates new entry.          */         Entry(int h, K k, V v, Entry<K,V> n) {             value = v;             next = n;             key = k;             hash = h;         }           public final K getKey() {             return key;         }           public final V getValue() {             return value;         }           public final V setValue(V newValue) {             V oldValue = value;             value = newValue;             return oldValue;         }           public final boolean equals(Object o) {             if (!(o instanceof Map.Entry))                 return false;             Map.Entry e = (Map.Entry)o;             Object k1 = getKey();             Object k2 = e.getKey();             if (k1 == k2 || (k1 != null && k1.equals(k2))) {                 Object v1 = getValue();                 Object v2 = e.getValue();                 if (v1 == v2 || (v1 != null && v1.equals(v2)))                     return true;             }             return false;         }           public final int hashCode() {             return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());         }           public final String toString() {             return getKey() + "=" + getValue();         }           /**     * 当entry的值通过调用put方法被重写时该方法将被调用          * This method is invoked whenever the value in an entry is          * overwritten by an invocation of put(k,v) for a key k that's already          * in the HashMap.          */         void recordAccess(HashMap<K,V> m) {         }           /**     * 当entry从table中删除时该方法将被调用          * This method is invoked whenever the entry is          * removed from the table.          */         void recordRemoval(HashMap<K,V> m) {         }     }

 

entry相关操作

/** * 添加一个新的entry。      * Adds a new entry with the specified key, value and hash code to      * the specified bucket.  It is the responsibility of this      * method to resize the table if appropriate.      *      * Subclass overrides this to alter the behavior of put method.      */     void addEntry(int hash, K key, V value, int bucketIndex) {         if ((size >= threshold) && (null != table[bucketIndex])) {             resize(2 * table.length);             hash = (null != key) ? hash(key) : 0;             bucketIndex = indexFor(hash, table.length);         }           createEntry(hash, key, value, bucketIndex);     }       /** * 创建entry，并将其添加到table[bucketIndex]队首中。      * Like addEntry except that this version is used when creating entries      * as part of Map construction or "pseudo-construction" (cloning,      * deserialization).  This version needn't worry about resizing the table.      *      * Subclass overrides this to alter the behavior of HashMap(Map),      * clone, and readObject.      */     void createEntry(int hash, K key, V value, int bucketIndex) {         Entry<K,V> e = table[bucketIndex];         table[bucketIndex] = new Entry<>(hash, key, value, e);         size++;     }

 

迭代。。。。（没看）

 

私有内部类KeySet及相关方法

// Views       private transient Set<Map.Entry<K,V>> entrySet = null;       /**      * Returns a {@link Set} view of the keys contained in this map.      * The set is backed by the map, so changes to the map are      * reflected in the set, and vice-versa.  If the map is modified      * while an iteration over the set is in progress (except through      * the iterator's own <tt>remove</tt> operation), the results of      * the iteration are undefined.  The set supports element removal,      * which removes the corresponding mapping from the map, via the      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>      * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>      * operations.      */     public Set<K> keySet() {         Set<K> ks = keySet;         return (ks != null ? ks : (keySet = new KeySet()));     }       private final class KeySet extends AbstractSet<K> {         public Iterator<K> iterator() {             return newKeyIterator();         }         public int size() {             return size;         }         public boolean contains(Object o) {             return containsKey(o);         }         public boolean remove(Object o) {             return HashMap.this.removeEntryForKey(o) != null;         }         public void clear() {             HashMap.this.clear();         }     }

 

私有内部类Value及其相关方法

/**      * Returns a {@link Collection} view of the values contained in this map.      * The collection is backed by the map, so changes to the map are      * reflected in the collection, and vice-versa.  If the map is      * modified while an iteration over the collection is in progress      * (except through the iterator's own <tt>remove</tt> operation),      * the results of the iteration are undefined.  The collection      * supports element removal, which removes the corresponding      * mapping from the map, via the <tt>Iterator.remove</tt>,      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,      * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not      * support the <tt>add</tt> or <tt>addAll</tt> operations.      */     public Collection<V> values() {         Collection<V> vs = values; // values属于AbstractMap的成员变量         return (vs != null ? vs : (values = new Values()));     }       private final class Values extends AbstractCollection<V> {         public Iterator<V> iterator() {             return newValueIterator();         }         public int size() {             return size;         }         public boolean contains(Object o) {             return containsValue(o);         }         public void clear() {             HashMap.this.clear();         }     }

 

私有内部类EntrySet及相关方法

/**      * Returns a {@link Set} view of the mappings contained in this map.      * The set is backed by the map, so changes to the map are      * reflected in the set, and vice-versa.  If the map is modified      * while an iteration over the set is in progress (except through      * the iterator's own <tt>remove</tt> operation, or through the      * <tt>setValue</tt> operation on a map entry returned by the      * iterator) the results of the iteration are undefined.  The set      * supports element removal, which removes the corresponding      * mapping from the map, via the <tt>Iterator.remove</tt>,      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and      * <tt>clear</tt> operations.  It does not support the      * <tt>add</tt> or <tt>addAll</tt> operations.      *      * @return a set view of the mappings contained in this map      */     public Set<Map.Entry<K,V>> entrySet() {         return entrySet0();     }       private Set<Map.Entry<K,V>> entrySet0() {         Set<Map.Entry<K,V>> es = entrySet;         return es != null ? es : (entrySet = new EntrySet());     }       private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {         public Iterator<Map.Entry<K,V>> iterator() {             return newEntryIterator();         }         public boolean contains(Object o) {             if (!(o instanceof Map.Entry))                 return false;             Map.Entry<K,V> e = (Map.Entry<K,V>) o;             Entry<K,V> candidate = getEntry(e.getKey());             return candidate != null && candidate.equals(e);         }         public boolean remove(Object o) {             return removeMapping(o) != null;         }         public int size() {             return size;         }         public void clear() {             HashMap.this.clear();           // HashMap.this值获取HashMap本身，所调用的clear即HashMap的方法         }     }

 

参考：

http://www.cnblogs.com/ITtangtang/p/3948406.html

http://blog.csdn.net/dyllove98/article/details/9207601