> 文档中心 > 哈希表的排序规则——HashCode编码

哈希表的排序规则——HashCode编码

力扣题387,官方答案第二种解法,哈希表存储索引。
针对答案遍历哈希表时产生疑惑,如果按照put存入哈希表的顺序排序的话,只需要找到第一个不为-1的value值就可以break跳出循环。

测试代码:

public class test02 {    public static void main(String[] args) { Map<String,Integer> map = new HashMap(); //添加元素 map.put("fafbb", 1242); map.put("gdada", 82); map.put("dgagg", 345); map.put("gdada", 5000);//key重复 map.put("kona", 345);//value重复 for(Object key:map.keySet()){  System.out.println(key+"\t"+map.get(key)); }    }}

输出:

fafbb1242kona345gdada5000dgagg345

从输出数据可以看出key值重复会被覆盖,而value值重复则没有影响。
从输出顺序可以看出,哈希表内部排序没有按照存入的顺序排序,同时也没有按照首字母升序或者降序来排序。

解释:
HashMap是一个最常用的Map,它根据键的hashCode值存储数据,按照HashCode编码进行从小到大的排序。在根据键可以直接获取它的值,具有很快的访问速度。HashMap最多只允许一条记录的键为NULL,允许多条记录的值为NULL。

HashCode编码:
HashCode的具体编码方式,比较复杂(事实上这个编码是可以由程序员通过继承和接口的实现重写的)。

解决:
利用LinkedHashMap创建哈希表。

    Map<String,Integer> map = new LinkedHashMap();

LinkedHashMap保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的。在遍历的时候会比HashMap慢TreeMap能够把它保存的记录根据键排序,默认是按升序排序,也可以指定排序的比较器。当用Iterator遍历TreeMap时,得到的记录是排过序的。

结论:
力扣提387需要通过以下代码完整遍历整个哈希表,找到最小的索引值。

 for (Map.Entry<Character, Integer> entry : position.entrySet()) {     int pos = entry.getValue();     if (pos != -1 && pos < first) {  first = pos;     } }