1. HashMap

1)  hashmap的数据结构 

     Hashmap是一个数组和链表的结合体（在数据结构称“链表散列“），如下图示：

        当我们往hashmap中put元素的时候，先根据key的hash值得到这个元素在数组中的位置（即下标），然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了，那么在同一个位子上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。

   

    

     

      

     
     

      

       <span style="font-size:18px;">Map map = new HashMap();  
      
     
    

     

      

     
     

      

       map.put("Rajib Sarma","100");  
      
     
    

     

      

     
     

      

       map.put("Rajib Sarma","200");//The value "100" is replaced by "200". 
      
     
    

     

      

     
     

      

       map.put("Sazid Ahmed","200");  
      
     
    

     

      

     
     

      
  
      
     
    

     

      

     
     

      

       Iterator iter = map.entrySet().iterator();  
      
     
    

     

      

     
     

      

       while (iter.hasNext()) {  
      
     
    

     

      

     
     

      

           Map.Entry entry = (Map.Entry) iter.next();  
      
     
    

     

      

     
     

      
    Object key = entry.getKey();  
      
     
    

     

      

     
     

      
    Object val = entry.getValue();  
      
     
    

     

      

     
     

      

       }  
      
     
    

     

      

     
     

      

       </span>  
      
     
   
  

2. HashTable和HashMap区别

第一，继承不同

public class Hashtable extends Dictionary implements Map
public class HashMap  extends AbstractMap implements Map

第二

Hashtable 中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下，可以直接使用Hashtable，但是要使用HashMap的话就要自己增加同步处理了。

第三

Hashtable中，key和value都不允许出现null值。

在HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，即可以表示 HashMap中没有该键，也可以表示该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。

第四，两个遍历方式的内部实现上不同。

Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式 。

第五

哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。

第六

Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。

LinkedHashMap实现类

1. LinkedHashMap概述：

1. LinkedHashMap概述：

LinkedHashMap是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用LinkedHashMap。

   LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
   LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
   注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。

根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用get方法)的链表。  

默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。  可以重写removeEldestEntry方法返回true值指定插入元素时移除最老的元素。

public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V> 

实例：

   

    

     

      

     
     

      

       package com.haixu.Map;  
      
     
    

     

      

     
     

      
  
      
     
    

     

      

     
     

      

       import java.util.LinkedHashMap;  
      
     
    

     

      

     
     

      
  
      
     
    

     

      

     
     

      

       public class LinkedHashtable {  
      
     
    

     

      

     
     

      
      
      
     
    

     

      

     
     

      
    public static void main(String[] args) {  
      
     
    

     

      

     
     

      
        LinkedHashMap lhp = new LinkedHashMap();  
      
     
    

     

      

     
     

      
          
      
     
    

     

      

     
     

      

               lhp.put("Spring" ,1 );  
      
     
    

     

      

     
     

      

               lhp.put("Struts" ,2 );  
      
     
    

     

      

     
     

      

               lhp.put("Hibernate" , 3);  
      
     
    

     

      

     
     

      
        for(Object key : lhp.keySet()){  
      
     
    

     

      

     
     

      

                   System.out.println(key + "--------------" + lhp.get(key));  
      
     
    

     

      

     
     

      

               }  
      
     
    

     

      

     
     

      

           }  
      
     
    

     

      

     
     

      
  
      
     
    

     

      

     
     

      

       }  
      
     
   
  

此处引入http://blog.csdn.net/hudashi/article/details/6944059的博

SortMap与TreeMap

接口SortedMap<K,V>
public interface SortedMap<K,V>
extends Map<K,V>
 保证按照键的升序排列的映射，可以按照键的自然顺序（参见 Comparable 接口）进行排序， 或者通过创建有序映射时提供的比较器进行排序。对有序映射的集合视图
 （由 entrySet、keySet 和 values 方法返回）进行迭代时，此顺序就会反映出来。
 要采用此排序，还需要提供一些其他操作（此接口是相似于 SortedSet 接口的映射）。
 插入有序映射的所有键都必须实现 Comparable 接口（或者被指定的比较器所接受）。
 另外，所有这些键都必须是可互相比较的：k1.compareTo(k2)（或 comparator.compare(k1, k2)）
 对有序映射中的任意两个元素 k1 和 k2 都不得抛出 ClassCastException。
 试图违反这些限制将导致违反方法或者构造方法的调用，从而抛出 ClassCastException。
 注意，如果有序映射正确实现了 Map 接口，则有序映射所保持的顺序（无论是否明确提供了比较器）都必须保持相等一致性。
 （相等一致性 的精确定义请参阅 Comparable 接口或 Comparator 接口）。
 这也是因为 Map 接口是按照 equals 操作定义的，但有序映射使用它的 compareTo（或 compare）方法对所有键进行比较，
 因此从有序映射的观点来看，此方法认为两个对象拥有相等的映射键则说明它们是相等的。
 即使顺序没有保持相等一致性，树映射的行为仍然是 定义良好的，只不过没有遵守 Map 接口的常规协定。
 所有通用有序映射实现类都应该提供 4 个“标准”构造方法：
 1) void（不带参数）构造方法，创建空的有序映射，按照键的自然顺序 排序。
 2) 带有一个 Comparator 类型参数的构造方法，创建一个空的有序映射，根据指定的比较器排序。
 3) 带有一个 Map 类型参数的构造方法，创建一个键-值映射关系与参数相同的有序映射，按照键的自然顺序排序。
 4) 带有一个有序映射类型参数的构造方法，创建一个新的有序映射，键-值映射关系及排序方法与输入的有序映射相同。如：TreeMap(SortedMap<K,? extends V> m) 
 除了 JDK 实现（TreeMap 类）遵循此建议外，无法保证强制实施此建议（因为接口不能包含构造方法）。
SortedMap声明的接口

实例：

   

    

     

      

     
     

      

       package com.haixu.Map;  
      
     
    

     

      

     
     

      
  
      
     
    

     

      

     
     

      

       import java.util.TreeMap;  
      
     
    

     

      

     
     

      
  
      
     
    

     

      

     
     

      

       class R implements Comparable{  
      
     
    

     

      

     
     

      
    int count;  
      
     
    

     

      

     
     

      
    public R (int count){  
      
     
    

     

      

     
     

      
        this.count = count;  
      
     
    

     

      

     
     

      

           }  
      
     
    

     

      

     
     

      
    public String toString(){  
      
     
    

     

      

     
     

      
        return "R[count:" + count + "]";  
      
     
    

     

      

     
     

      

           }  
      
     
    

     

      

     
     

      
    public boolean equals (Object obj){  
      
     
    

     

      

     
     

      
        if(this == obj)  
      
     
    

     

      

     
     

      
            return true;  
      
     
    

     

      

     
     

      
        if(obj != null && obj.getClass() == R.class){  
      
     
    

     

      

     
     

      
            R r = (R) obj;  
      
     
    

     

      

     
     

      
            return r.count == this.count;  
      
     
    

     

      

     
     

      

               }  
      
     
    

     

      

     
     

      
        return false;  
      
     
    

     

      

     
     

      

           }  
      
     
    

     

      

     
     

      
    public int compareTo(Object obj){  
      
     
    

     

      

     
     

      
        R r = (R) obj;  
      
     
    

     

      

     
     

      
        return count > r.count ? 1 : count < r.count -1 ? -1:0;  
      
     
    

     

      

     
     

      

           }  
      
     
    

     

      

     
     

      

       }  
      
     
    

     

      

     
     

      
  
      
     
    

     

      

     
     

      
  
      
     
    

     

      

     
     

      

       public class TreeMapTest {  
      
     
    

     

      

     
     

      
      
      
     
    

     

      

     
     

      
    public static void main(String[] args) {  
      
     
    

     

      

     
     

      
        TreeMap tm = new TreeMap();  
      
     
    

     

      

     
     

      

               tm.put(new R(2), "struts");  
      
     
    

     

      

     
     

      

               tm.put(new R(1), "Spring");  
      
     
    

     

      

     
     

      

               tm.put(new R(3),"Hibernate");  
      
     
    

     

      

     
     

      
          
      
     
    

     

      

     
     

      

               System.out.println(tm);  
      
     
    

     

      

     
     

      
          
      
     
    

     

      

     
     

      

              System.out.println(tm.firstEntry());  
      
     
    

     

      

     
     

      
         
      
     
    

     

      

     
     

      

              System.out.println(tm.lastKey());  
      
     
    

     

      

     
     

      
         
      
     
    

     

      

     
     

      

              System.out.println(tm.higherKey(new R(2)));  
      
     
    

     

      

     
     

      
         
      
     
    

     

      

     
     

      

              System.out.println(tm.subMap(new R (2), new R(3)));  
      
     
    

     

      

     
     

      

           }  
      
     
    

     

      

     
     

      
      
      
     
    

     

      

     
     

      
  
      
     
    

     

      

     
     

      

       }  
      
     
   
  

   

    

     

      

     
     

      

       {R[count:2]=Spring, R[count:3]=Hibernate}  
      
     
    

     

      

     
     

      

       R[count:2]=Spring  
      
     
    

     

      

     
     

      

       R[count:3]  
      
     
    

     

      

     
     

      

       null  
      
     
    

     

      

     
     

      

       {}