哈希表的排序规则——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+"	"+map.get(key));
        }
    }
}

输出：

fafbb	1242
kona	345
gdada	5000
dgagg	345

从输出数据可以看出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;
            }
        }