数据结构_map、set、哈希表(概念、方法、冲突、代码实现)_map 和hash表

一、Map

概念：Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。

1、Map的相关说明

常用方法
 1. V get(Object key)  [返回 key 对应的 value]
 2. V put(K key, V value)  [设置 key 对应的 value]
 3. V remove(Object key)  [删除 key 对应的映射关系]
 4. boolean containsKey(Object key) [判断是否包含 key]
注意事项：
 1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
 2. Map中存放键值对的Key是唯一的，value是可以重复的
 3. 在TreeMap中插入键值对时，key不能为空，否则就会抛NullPointerException异常，value可以为空。但
是HashMap的key和value都可以为空。
 4. Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
 5. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
 6. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行
重新插入

2、TreeMap和HashMap

二、Set

Set也是继承自Collection的接口类，Set中只存储了Key，不储存Value

1. Set相关说明

常用方法
  1. boolean add(E e)  [添加元素，但重复元素不会被添加成功]
  2. boolean contains(Object o)  [判断 o 是否在集合中]
  3. boolean remove(Object o)   [删除集合中的 o]
  4. Object[] toArray()   [将set中的元素转换为数组返回]
注意事项
  1. Set是继承自Collection的一个接口类
  2. Set中只存储了key，并且要求key一定要唯一
  3. TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
  4. Set最大的功能就是对集合中的元素进行去重
  5. 实现Set接口的常用类有TreeSet和HashSet
  6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
  7. TreeSet中不能插入null的key，HashSet可以

2.TreeSet和HashSet

三、哈希表

如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素.当向该结构中：
插入元素
  根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素
 对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
  该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash
Table)(或者称散列表)**

哈希函数设置:
  哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小

1. Hash冲突

  不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞

2. 冲突-避免-负载因子调节

散列表的负载因子定义：
  负载因子 = 填入表中的元素个数 / 散列表长度
  在JAVA中负载因子设为 0.75，超过此值将对散列表长度进行扩容。已知哈希表中已有的关键字个数是不可变的，那能调整的就只有哈希表中的数组的大小。

3. 冲突-解决

1）. 线性探测

  从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止，插入新元素。

2）.二次探测

重设Hash函数
H(i) = (H(0) (±) i^2) % length;

3). 哈希桶

  开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

代码实现

package Demo;

/**
 * @author ZhangXu
 * @date 2024/3/2417:50
 * @Description:
 */
public class HashBuck {

    //key-Value 模型
    static  class  Node{
        private   int key;
        private   int value;
        public  Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Node[] array;
    private  int usedSize;  //当前数据的个数
    private  static  final double LOAD_FACTOR = 0.75;
    public HashBuck(){
        array = new Node[10];
    }

    public void put(int key,int value){
        int index = key %array.length;
        Node cur = array[index];
        //遍历index下标的链表，是否存在key, 若存在更新value;若不存在，则采用头插法插入数据
        while (cur != null){
            if (cur.key == key){
                //更新value
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        //cur  = null ,链表遍历完成，没有找到key
        Node node = new Node(key,value);
        node.next = array[index];
        array[index] = node;
        usedSize++;

        if (loadFactor() >= LOAD_FACTOR){
            resize();
        }
    }

    private void resize() {
        Node[] Newarray = new Node[2*array.length];

        //遍历原来的数组
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            //遍历每个人数组元素的链表
            while (cur != null){
                Node tmp = cur.next;
                int NewIndex = cur.key % Newarray.length; //新的数组下标
                //采用头插法，插入到新数组的NewIndex下标
                cur.next = Newarray[NewIndex];
                Newarray[NewIndex] = cur;
                cur =  tmp;
            }
        }
        array = Newarray;
    }

    public int get(int key){
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null){
            if (cur.key == key){
                return cur.value;
            }
            cur = cur.next;
        }
        return -1;
    }
    /**
     * 计算负载因子
     * @return
     */
    private double loadFactor(){
        return usedSize*1.0/array.length;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89