hahMap 的数据结构 、遍历以及排序

HashMap的遍历

1、ha'shMap的数据结构

其实hashMap 是一个链表的数组，内部是一个存储着链表表头的数组（图片来自其他博客），一般都是key对应的hash值就是该元素在数组的下标。

HashMap里边实现一个静态内部类Entry（key，value，next），所以说的数组就是一个Entry[] 数组。

2、hashMap的遍历

（1）.entrySet()返回的是特殊的Set集合。set的Iterator() 返回一个EntryIterator类型的实例。

  HashMap map = new HashMap(); 

          Iterator it = map.entrySet().iterator();
          while(it.hasNext()){
        Map.Entry entry = (Entry) it.next(); 
    Object key = entry.getKey();
    Object value = entry.getValue();
          }

          （2）. 遍历keySet

for(String key:map.keySet()){
        String value = map.get(key);
        }

    以上两种方式，第一种的效率高，因为只遍历hashMap一次，将映射关系存入set中。而第二种方式需要先遍历key，再根据key遍历value。

3、排序HashMap

java.util.HashMap<Integer,Integer> map = new java.util.HashMap<Integer,Integer>();

List<Map.Entry<Integer, Integer>> infoIds =  new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
        
        Collections.sort(infoIds, new Comparator<Map.Entry<Integer, Integer>>() {   
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {      
                return (o2.getValue() - o1.getValue()); 
                //return (o1.getKey()).compareTo(o2.getKey());
            }
        });

   题外：排序问题

     (1)、类需要比较  可以实现Comparable接口

    接口中有一个方法  comparableTo()，可以在类中实现（一下代码来自博客http://blog.****.net/memewry/article/details/7907012）

1. public int compareTo(User arg0) {  
2.         return this.getOrder().compareTo(arg0.getOrder());  
3.     }  

    （2）、java.util下有一个Comparator（比较器）。它拥有compare( )方法，用来比较两个对象

比如上边HashMap 排序时用到的比较器