1.HashMap

  《1》遍历：HashMap无序遍历

    for(Map.Entry<String, String>m: map.entrySet()//键值对，允许键为空String

        {

            System.out.println(m.getKey()+" : "+m.getValue());

        }

 HashMap 源码：

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;
    ……
}

添加元素

      public V put(K key, V value) {
   // HashMap允许存放null键和null值。
   // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。
   if (key == null)
       return putForNullKey(value);
   // 根据key的keyCode重新计算hash值。
   int hash = hash(key.hashCode());
   // 搜索指定hash值在对应table中的索引。
   int i = indexFor(hash, table.length);
   // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。
   for (Entry<K,V> e = table[i]; e != null; e = e.next) {
       Object k;
      // 如果发现 i 索引处的链表的某个Entry的hash和新Entry的hash相等且两者的key相同，则新Entry覆盖旧Entry，返回。
       if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
           V oldValue = e.value;
           e.value = value;
           e.recordAccess(this);
           return oldValue;
       }
   }
   // 如果i索引处的Entry为null，表明此处还没有Entry。
   modCount++;
   // 将key、value添加到i索引处。
   addEntry(hash, key, value, i);
   return null;

读取元素

   

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = 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.equals(k)))
            return e.value;
    }
    return null;
}

String equals

   

 /**
    * Compares this string to the specified object.  The result is {@code
    * true} if and only if the argument is not {@code null} and is a {@code
    * String} object that represents the same sequence of characters as this
    * object.
    *
    * @param  anObject
    *         The object to compare this {@code String} against
    *
    * @return  {@code true} if the given object represents a {@code String}
    *          equivalent to this string, {@code false} otherwise
    *
    * @see  #compareTo(String)
    * @see  #equalsIgnoreCase(String)
    */
   public boolean equals(Object anObject) {
if (this == anObject) {
    return true;
}
if (anObject instanceof String) {
    String anotherString = (String)anObject;
    int n = count;
    if (n == anotherString.count) {
    char v1[] = value;
    char v2[] = anotherString.value;
    int i = offset;
    int j = anotherString.offset;
    while (n-- != 0) {
        if (v1[i++] != v2[j++])
        return false;
    }
    return true;
    }
}
return false;
   }

String hashcode

  /**
    * Returns a hash code for this string. The hash code for a
    * <code>String</code> object is computed as
    * <blockquote><pre>
    * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
    * </pre></blockquote>
    * using <code>int</code> arithmetic, where <code>s[i]</code> is the
    * <i>i</i>th character of the string, <code>n</code> is the length of
    * the string, and <code>^</code> indicates exponentiation.
    * (The hash value of the empty string is zero.)
    *
    * @return  a hash code value for this object.
    */
   public int hashCode() {
int h = hash;
       int len = count;
if (h == 0 && len > 0) {
    int off = offset;
    char val[] = value;

           for (int i = 0; i < len; i++) {
               h = 31*h + val[off++];
           }
           hash = h;
       }
       return h;
   }

hash函数

/**
    * Applies a supplemental hash function to a given hashCode, 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.
    */
tatic int hash(int h) {
       // 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);
   }

   /**
    * Returns index for hash code h.
    */
 static int indexFor(int h, int length) {
       return h & (length-1);
}