Hash 函数

2021-09-02

Hash结构

数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)

线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)
二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。
哈希表：在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)。
我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。
　　比如我们要新增或查找某个元素，我们通过把当前元素的关键字通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。
　　 location = hash(关键字)
其中，hash函数设计的优劣直接影响整体的性能。

哈希冲突：哈希算法存在一个缺点就是哈希冲突。例如，我们进行数据存储时，我们通过对关键字进行hash时得到的地址已经存储过数据了，这时就会出现哈希冲突。因此，哈希函数的设计至关重要，好的哈希函数会尽可能地保证计算简单和散列地址分布均匀。但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式。

HashMap的用法

Collection中的集合，元素是孤立存在的，向集合中存储元素采用一个个元素的方式存储。

Map中的集合，元素是成对存在的(key[键],value[值])。每个元素由键与值两部分组成，通过键可以找对所对应的值。

Collection中的集合称为单列集合，Map中的集合称为双列集合。

需要注意的是，Map中的集合不能包含重复的键，值可以重复；每个键只能对应一个值。

Map中常用的集合为HashMap集合、LinkedHashMap集合。

HashMap<K,V>：存储数据采用的哈希表结构，元素的存取顺序不能保证一致。由于要保证键的唯一、不重复，需要重写键的hashCode()方法、equals()方法。

LinkedHashMap<K,V>：HashMap下有个子类LinkedHashMap，存储数据采用的哈希表结构+链表结构。通过链表结构可以保证元素的存取顺序一致；通过哈希表结构可以保证的键的唯一、不重复，需要重写键的hashCode()方法、equals()方法。

注意：Map接口中的集合都有两个泛型变量<K,V>,在使用时，要为两个泛型变量赋予数据类型。两个泛型变量<K,V>的数据类型可以相同，也可以不同。

Map接口的常用方法

get(Object key)：返回指定键所映射的值，如果没有映射关系返回null。
put(K key,V value)：将指定的值与指定键关联，让它们产生联系(可选操作)。
remove(Object key)：如果存在一个键的映射关系，则将其从此映射中移除(可选操作)。

Map的遍历

使用keySet()遍历；

public class HashMap_Demo {
    public static void main(String[] args) {
        HashMap<String ,String> weather = new HashMap<>();
        weather.put("温州","晴天");
        weather.put("杭州","雨天");
        weather.put("北京","阴天");

        Set<String> keyset = weather.keySet();

        for (String x:keyset) {
            String key = x;
            String value = weather.get(x);
            System.out.println(key+"今天是"+value);
        }
        
        // Iterator<String> iterator =weather.keySet().iterator();
        // while(iterator.hasNext()){
        //     String key = iterator.next();
        //     String value = weather.get(key);
        //     System.out.println(key+"今天是"+value);
        // }这边是迭代器遍历,推荐foreach，效率高性能好。
    }
    /*运行结果：温州 晴天
               杭州 雨天
               北京 阴天
    */
}

使用entrySet()方法遍历；//感觉不好用

public class HashMap_Demo {
    public static void main(String[] args) {
        HashMap<String ,String> weather = new HashMap<>();
        weather.put("温州","晴天");
        weather.put("杭州","雨天");
        weather.put("北京","阴天");
        
        Set<Map.Entry<String, String>> keyset = weather.entrySet();

         for (Map.Entry<String, String> x:keyset) {
            String key = x.getKey();
            String value=x.getValue();
            System.out.println(key+" "+value);
        }

        // Iterator<Map.Entry<String, String>> iterator = keyset.iterator();
        // while(iterator.hasNext()){
        //     Map.Entry<String,String> it = iterator.next();
        //     String key = it.getKey();
        //     String value=it.getValue();//String data = weather.get(key);这也行
        //     System.out.println(key+" "+value);
        // }迭代器还是麻烦
        
        /*运行结果：温州 晴天
               杭州 雨天
               北京 阴天
    */
    }
}

使用entrySet，其内部自带个已声明泛型接口map.Entry。
其下还有2个方法，getKey()与getValue()都可以方便(麻烦)获取值。
map.Entry<String,String>//貌似可以当int声明。
可以看作是饥荒打克劳斯掉的包裹(只有两格)。
没错，打包了key与value。再塞给set。。

Hashtable的用法

Hashtable里也有key和value，但是一般情况key是放int型，value是String型，因为乱放顺序可能会乱(key是String型)。

Hashtable hashtable = new Hashtable();
        hashtable.put(1 ,"a");
        hashtable.put(2 ,"b");
        hashtable.put(3,"c");

看起来很简单，但我感觉没Map好用。
hashtable.remove(key值)会删除那一条并返回对应value。
hashtable.get(k值)返回对应value。
hashtable.values()以集合形式(Collection 可以声明)返回所有的value。
hashtable.contains(value)返回t或f。
hashtable.keys()返回Enumeration(枚举类？)型的枚举键集。
hashtable.elements()返回Enumeration(枚举类？)型的枚举值集。
hashtable.keyset()一般配合Set用，把key变成放到set里吧？
用keySet获取key键：

Set keyset = hashtable.keySet();  //keySet感觉更像是打包，原属性不变丢过去。
for (Object x : keyset){//Object要转换下
            Integer key = (Integer)x; 
            String value = (String) hashtable.get(x);
            System.out.println("key:"+key+"value:"+value);
        }

以下是用迭代器遍历

Set keyset = hashtable.keySet();
Iterator iterator =keyset.iterator();
while(iterator.hasNext()) {
    Integer key = (Integer) iterator.next();    //获取key，这里hashtable的key在表面是int型的
    String value = (String)hashtable.get(iterator.next());  //获取value，这里表面是String型的
    System.out.println("key:"+key+"  "+"value:"+value);
}//不知道咋地抽风，本来可以的

运行结果应该是一致的：
key:3 value:c
key:2 value:b
key:1 value:a
以下是2种value遍历

Collection tvalue = hashtable.values();
for (Object x : tvalue){
    System.out.print(x+" "); //这种方法只能输出值
}

另一个方法

Collection dvalue = hashtable.values();
Iterator iteratorr = dvalue.iterator();
while (iteratorr.hasNext()){
    String value = (String)iteratorr.next();
    System.out.print(value+" ");
}

以下是2种古老？方法的遍历(Enumeration)
先来看看Enumeration，翻译是枚举，看起来是枚举类？可以拿来声明。

for (Enumeration en = hashtable.keys(); en.hasMoreElements()//配合Enumeration,意思为下一个字符串存在就返回true;//不填) {
    System.out.print(en.nextElement()//下一个元素+" ");
}//这边返回键
System.out.println();
for (Enumeration an = hashtable.elements();an.hasMoreElements();){
    System.out.print(an.nextElement()+" ");
}//同理可得

运行结果：
3 2 1
c b a