Map and Set

map and set

文章目录

map and set
- 前言
- 搜索树
- - <1> 操作-查找
  - <2> 操作-插入
  - <3> 操作-删除
  - <4> 代码展示
  - <5> 性能分析
- Map 和 Set 概念及应用场景
- Map 和 Set 模型分析
- Map 的使用
- - <1> Map常用方法说明
  - <3> TreeMap 演示
  - <2> Entry 内部接口
  - <3> Map 中注意事项
  - <4> 遍历 Map 的四种方法
- Set 的使用
- - <1> Set 常用方法说明
  - <2> TreeSet 演示
  - <3> Set 中注意事项
- 哈希表
- - <1> 概念
  - <2> 哈希函数
  - <3> 哈希冲突-避免
  - <4> 负载因子
  - <5> 解决哈希冲突-开散列/哈希桶
- 哈希桶的实现
- OJ练习

前言

在讲 Map 和 set之前。我们要对其有个简单的了解。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

对于 set 和 map 接口来说，二者分别包含了 TreeSet、HashSet 和 TreeMap、HashMap 工具类。

TreeMap 和 TreeSet 的底层是一颗二叉搜索树，这颗搜索树是一颗红黑树。对于二叉搜索树来说，每次插入节点，都需要有一个大小的比较，因此 set 和 map 分别实现了 SortedSet 和 SortedMap 这两个接口。

HashMap 和 HashSet 的底层是一个哈希桶。

本篇重点讲解：

二叉搜索树
哈希桶
Map 和 Set 方法使用及说明

搜索树

性质：

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右字数也分别为二叉搜索树

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

接下来简单来实现搜索树的几个方法：1.查找 2.插入 3.删除

<1> 操作-查找

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

假设现在要查找一个数 val= 0 ；

查找方法：

如果根节点 cur == val 则找到了，返回 true.
如果根节点 cur > val ，在其左子树继续查找。
若果根节点 cur < val ，在其右子树继续查找。

实现代码如下：

public TreeNode search(int val) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val == val) {
            return cur;
        } else if (cur.val > val) {
            cur = cur.left;
        } else {
            cur = cur.right;
        }
    }
    return null;
}

<2> 操作-插入

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

当树为空时：要插入的节点就是根节点，即 root = node
当树不为空时：就相当于找空位置坐下。
- 如果根节点 cur == val 则说明相同的节点已存在，插入失败，返回 false.
- 如果根节点 cur > val ，在其左子树继续找位置坐。
- 若果根节点 cur < val ，在其右子树继续找位置坐。
当我们找位置坐的时候，一旦找到 ( cur == null )，就无法确定 cur 的父亲节点是啥了。因此要定义一个 parent 节点，来记录 cur 的上一个节点。

实现代码如下：

public boolean insert(int key) {
    TreeNode node = new TreeNode(key);

    TreeNode cur = root;
    TreeNode parent = null;

    if (cur == null) {
        root = node;
        return true;
    }

    while (cur != null) {
        if (cur.val > key) {
            parent = cur;
            cur = cur.left;
        } else if (cur.val < key) {
            parent = cur;
            cur = cur.right;
        } else {
            return false;
        }
    }

    if (parent.val > key) {
        parent.left = node;
    } else {
        parent.right = node;
    }
    UsedSize++;
    return true;
}

<3> 操作-删除

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

注：待删除的节点为 cur，待删除的双亲节点为 parent

当 cur.left == null 时
- cur 是 root，则 root = cur.right
- cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
- cur 不是 root，cur 是 parent.right，则 parent.right = cur.right
当 cur.right == null 时
- cur 是 root，则 root = cur.right
- cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
- cur 不是 root，cur 是 parent.right，则 parent.right = cur.right
当 cur 的左子树/右子树均不为空时

需要用到替罪羊法进行删除。当左右均不为 null 时，删除一个节点就需要对下面的子树进行调整，因此我们会想到替罪羊方法。

替罪羊法：找到左树的最小节点，或者右树的最大节点，插入到这个删除的节点中。

代码实现如下：

public boolean removNode(int key) {
    TreeNode cur = root;
    TreeNode parent = null;

    while (cur != null) {
        if (cur.val > key) {
            parent = cur;
            cur = cur.left;
        } else if (cur.val < key) {
            parent = cur;
            cur = cur.right;
        } else {
            Remove(cur, parent);
            return true;
        }
    }
    return false;
}

private void Remove(TreeNode cur, TreeNode parent) {
    if (cur.left == null) {
        if (cur == root) {
            root = cur.right;
        } else if (parent.left == cur) {
            parent.left = cur.right;
        } else {
            parent.right = cur.right;
        }
    } else if (cur.right == null) {
        if (cur == root) {
            root = cur.left;
        } else if (parent.left == cur) {
            parent.left = cur.left;
        } else {
            parent.right = cur.right;
        }
    } else {
        TreeNode targetPartent = cur;
        TreeNode target = cur.right;

        while (target.left != null) {
            targetPartent = target;
            target = target.left;
        }

        cur.val = target.val;

        if (targetPartent.left == target) {
            targetPartent.left = target.right;
        } else {
            targetPartent.right = target.right;
        }
    }
}

<4> 代码展示

以上就是我们简单实现的搜索二叉树，下面展示全部代码（测试代码就不予展示）：

public class BinarySearchTree {

    static class TreeNode {
        private int val;
        public TreeNode right;
        public TreeNode left;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public int UsedSize;

    public TreeNode root;

    public TreeNode search(int val) {

        TreeNode cur = root;
        while (cur != null) {
            if (cur.val == val) {
                return cur;
            } else if (cur.val > val) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return null;
    }
    public boolean insert(int key) {
        TreeNode node = new TreeNode(key);

        TreeNode cur = root;
        TreeNode parent = null;

        if (cur == null) {
            root = node;
            return true;
        }

        while (cur != null) {
            if (cur.val > key) {
                parent = cur;
                cur = cur.left;
            } else if (cur.val < key) {
                parent = cur;
                cur = cur.right;
            } else {
                return false;
            }
        }

        if (parent.val > key) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        UsedSize++;
        return true;
    }

    public boolean removNode(int key) {
        TreeNode cur = root;
        TreeNode parent = null;

        while (cur != null) {
            if (cur.val > key) {
                parent = cur;
                cur = cur.left;
            } else if (cur.val < key) {
                parent = cur;
                cur = cur.right;
            } else {
                Remove(cur, parent);
                return true;
            }
        }
        return false;
    }

    private void Remove(TreeNode cur, TreeNode parent) {
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            } else if (parent.left == cur) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            } else if (parent.left == cur) {
                parent.left = cur.left;
            } else {
                parent.right = cur.right;
            }
        } else {
            TreeNode targetPartent = cur;
            TreeNode target = cur.right;

            while (target.left != null) {
                targetPartent = target;
                target = target.left;
            }

            cur.val = target.val;

            if (targetPartent.left == target) {
                targetPartent.left = target.right;
            } else {
                targetPartent.right = target.right;
            }
        }
    }
}

<5> 性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个数据集合，如果数据插入的次序不同，可能得到不同结构的二叉搜索树：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

**最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：**log₂N

**最差情况下，二叉搜索树退化为单支树，其平均比较次数为：**N/2

Map 和 Set 概念及应用场景

Map 和 set 是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。

以前常见的搜索方式有：

直接遍历，时间复杂度为O(N)，元素比较多效率就会非常慢。
二分查找，时间复杂度为O(log₂N)，但搜索前数据必须是有序的。

上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作。而现实中的查找却并非如此，通常会夹杂着插入以及删除操作，即动态查找，本篇介绍的 Map 和 Set 则是一种适合动态查找的容器。

Map 和 Set 模型分析

一般把搜索的数据称为关键字 (Key)，和关键字对应的称为值 (Value)，将其称之为 Key-value 的键值对，所以模型会有两种：

纯 Key 模型：

例：快速查找某个 名字(key) 在不在通讯录中。
Key-Value 模型：

例：查找某个 单词(key) 在字典中出现的 次数(value)。

Map 中存储的就是 Key-value 的键值， Set 中只存储了 Key.

Map 的使用

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

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

map 实现了 SortedMap 这个抽象类

<1> Map常用方法说明

方法	解释
V get(Object key)	返回 key 对应的 value
V getOrDefault(Object key, V defaultValue)	返回 key 对应的 value，key 不存在，返回默认值
V put(K key, V value)	设置 key 对应的 value
V remove(Object key)	删除 key 对应的映射关系
Set keySet()	返回所有 key 的不重复集合
Collection values()	返回所有 value 的可重复集合
Set<Map.Entry<K, V>> entrySet()	返回所有的 key-value 映射关系
boolean containsKey(Object key)	判断是否包含 key
boolean containsValue(Object value)	判断是否包含 value

<3> TreeMap 演示

public static void main(String[] args) {
    Map<String, String> map = new TreeMap();

    map.put("Key1", "Value1");
    map.put("Key2", "Value2");
    map.put("Key3", "Value3");
    map.put("Key4", "Value4");
    map.put("Key5", "Value5");

    System.out.println(map.getOrDefault("aaa", "nothing"));  //nothing

    map.put("Key1", "aaa");           //修改 Key1 的值为aaa

    Set<String> set = map.keySet();
    System.out.println(set);          //[Key1, Key2, Key3, Key4, Key5]

    Collection<String> collection = map.values();
    System.out.println(collection);              //[Value1, Value2, Value3, Value4, Value5]
}

<2> Entry 内部接口

Entry 是 java 为 Map 提供的内部接口，其主要提供 getKey()、getValue()、setValue()… 等方法。

Map 中提供的 entrySet 方法，用 Set 来存储，返回值类型是 Map.Entry<K, V>。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

public static void main(String[] args) {
    Map<String, String> map = new TreeMap();

    map.put("Key1", "Value1");
    map.put("Key2", "Value2");
    map.put("Key3", "Value3");
    map.put("Key4", "Value4");
    map.put("Key5", "Value5");

    Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
    for (Map.Entry<String, Integer> entry : entrySet) {
        System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
    }
}

打印结果：
key= Key1 and value= Value1
key= Key2 and value= Value2
key= Key3 and value= Value3
key= Key4 and value= Value4
key= Key5 and value= Value5

<3> Map 中注意事项

Map 是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类 TreeMap 或者 HashMap.
Map 中存放键值对的Key是唯一的，value是可以重复的.
在 TreeMap 中插入键值对时，value 可以为空，key 不能为空，否则就会抛 NullPointerException 异常。但是 HashMap 的 key 和 value 都可以为空。
Map 中的 Key 可以全部分离出来，存储到 Set 中来进行访问(因为Key不能重复)。
Map 中的 value 可以全部分离出来，存储在 Collection 的任何一个子集合中(value可能有重复)。
Map 中键值对的 Key 不能直接修改，value 可以修改，如果要修改 key，只能先将该 key 删除掉，然后再来进行重新插入。

TreeMap 和 HashMap 的区别。

Map底层结构	TreeMap	HashMap
底层结构	红黑树	Hash桶
插入/删除/查找时间复杂度	O(log₂N)	O(1)
是否有序	关于Key有序	无序
线程安全	不安全	不安全
插入/删除/查找区别	需要进行元素比较	通过哈希函数计算哈希地址
比较与覆写	key必须能够比较，否则会抛出 ClassCastException 异常	自定义类型需要覆写equals和hashCode方法
应用场景	需要Key有序场景下	Key是否有序不关心，需要更高的时间性能

<4> 遍历 Map 的四种方法

public static void main(String[] args) {
    Map<String, String> map = new HashMap<String, String>();
    
    map.put("1", "value1");
    map.put("2", "value2");
    map.put("3", "value3");

    //第一种：普遍使用，二次取值,效率较低
    System.out.println("通过Map.keySet遍历key和value：");
    for (String key : map.keySet()) {
        System.out.println("key= "+ key + " and value= " + map.get(key));
    }

    //第二种
    System.out.println("通过Map.entrySet使用iterator遍历key和value：");
    Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry<String, String> entry = it.next();
        System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
    }

    //第三种：推荐，尤其是容量大时，效率较高
    System.out.println("通过Map.entrySet遍历key和value");
    for (Map.Entry<String, String> entry : map.entrySet()) {
        System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
    }

    //第四种
    System.out.println("通过Map.values()遍历所有的value，但不能遍历key");
    for (String v : map.values()) {
        System.out.println("value= " + v);
    }
}

Set 的使用

说明：Set 与 Map 主要的不同有两点：Set 是继承自 Collection 的接口类，Set 中只存储了 Key。

![外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传](https://img-blog.csdnimg.cn/c319b753c79f4310a8966347b757f2ad.png)

<1> Set 常用方法说明

方法	解释
boolean add(E e)	添加元素，但重复元素不会被添加成功
void clear()	清空集合
boolean contains(Object o)	判断 o 是否在集合中
Iterator iterator()	返回迭代器
boolean remove(Object o)	删除集合中的 o
int size()	返回set中元素的个数
boolean isEmpty()	检测set是否为空，空返回true，否则返回false
Object[] toArray()	将set中的元素转换为数组返回
boolean containsAll(Collection<?> c)	集合c中的元素是否在set中全部存在，是返回true，否则返回false
boolean addAll(Collection<? extends E> c)	将集合c中的元素添加到set中，可以达到去重的效果

<2> TreeSet 演示

public static void main(String[] args) {
    Set<String> set = new TreeSet<>();

    set.add("hello");
    set.add("world");
    set.add("abcd");

    Iterator<String> it = set.iterator();
    while (it.hasNext()) {
        System.out.println(it.next());         
    }

    System.out.println(set.contains("hello"));  // true

    System.out.println(set.remove("abcd"));     //true

    System.out.println(set.size());             // 2

    System.out.println(set.containsAll(set));   //true
}

<3> Set 中注意事项

Set 是继承自 Collection 的一个接口类。
Set 中只存储了 key，并且要求 key 一定要唯一。
TreeSet 的底层是使用 Map 来实现的，其使用 key 与 Object 的一个默认对象作为键值对插入到 Map 中的。
Set 最大的功能就是对集合中的元素进行去重。
实现 Set 接口的常用类有 TreeSet 和 HashSet，还有一个 LinkedHashSet，LinkedHashSet 是在 HashSet 的基础上维护了一个双向链表来记录元素的插入次序。
Set 中的 Key 不能修改，如果要修改，先将原来的删除掉，然后再重新插入。
TreeSet 中不能插入 null 的 key，HashSet 可以。

TreeSet 和 HashSet 的区别。

Set 底层结构	TreeSet	HashSet
底层结构	红黑树	哈希桶
插入/删除/查找时间复杂度	O(log₂N)	O(1)
是否有序	关于 key 有序	不一定有序
线程安全	不安全	不安全
插入/删除/查找区别	按照红黑树的特性来进行插入和删除	先计算 key 哈希地址然后进行插入和删除
比较与覆写	key 必须能够比较，否则会抛出 ClassCastException异常	自定义类型需要覆写 equals 和 hashCode方法
应用场景	需要 Key 有序场景下	Key 是否有序不关心，需要更高的时间性能

哈希表

<1> 概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log₂N)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

该理想结构中：

插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希方法，哈希方法中使用的转换函数称为哈希函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)

<2> 哈希函数

例如：数据集合{1，7，6，4，5，9}；此数据该如何存储？？

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。计算出来的哈希值就是要存储的数组下标。

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

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

用该方法进行搜索不必进行多次关键码的比较，因此搜索/插入的速度比较快

<3> 哈希冲突-避免

问题：按照上述哈希方式，向集合中插入元素 44，会出现什么问题？

会插入到下标为 4 的数组，有可能会覆盖之前插入的数据 14。不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

常见哈希函数：

直接定制法

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀缺点：需要事先知道关键字的分布情况。

使用场景：适合查找比较小且连续的情况
除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数：Hash(key) = key % p(p<=m)，将关键码转换成哈希地址。

<4> 负载因子

散列表的载荷因子定义为: Q = 填入表中的元素个数 / 散列表的长度

负载因子和冲突率的粗略图：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

在哈希表中，负载因子是一个重要的参数，它决定了哈希表的性能和空间利用率。负载因子太低会导致大量的空桶浪费空间，负载因子太高会导致大量的碰撞，降低性能。通常情况下，0.75 的负载因子在空间利用率和性能之间取得了良好的平衡。

所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。**已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。**在Java中的HashMap中，负载因子是一个重要的参数，当HashMap中的元素个数超过了容量乘以负载因子时，就会进行扩容。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

<5> 解决哈希冲突-开散列/哈希桶

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

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

上面提到了，哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了，那如果冲突严重，就意味着小集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如：

每个桶的背后是另一个哈希表
每个桶的背后是一棵搜索树

哈希桶的实现

实现的此哈希桶，其负载因子为 0.75，哈希函数为 hash = key % capacity .

原理：数组里面套链表。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

代码实现如下：

public class HashBucket {

    static class Node {
        private int key;
        private int value;
        private Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    public Node[] array;
    public int usedSize;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;   //默认负载因子大小 0.75
    
    public HashBucket () {
        this.array = new Node[10];   //构造方法中初始化容量capacity为10
    }

    public void put (int key, int val) {
        Node node = new Node(key, val);
        int index = key % array.length;

        Node cur = array[index];

        while (cur != null) {
            if (cur.key == key) {
                cur.value = val;
                return;
            }
            cur = cur.next;
        }
        node.next = array[index];
        array[index] = node;

        usedSize ++;

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

    private float loadFactor() {         //计算负载因子
        return usedSize*1.0f / array.length;
    }

    private void resize () {             //负载因子过大，进行扩容
        Node[] tmpArray = new Node[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                Node curNext = cur.next;
                int index = cur.key % tmpArray.length;

                cur.next = tmpArray[index];
                tmpArray[index] = cur;

                cur = curNext;
            }
        }
        array = tmpArray;
    }

    public int getValue(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;
    }
}

结合泛型代码如下：

注意：

因为 key 不是具体的数值，而是一个对象，因此要用到 hashcode() 来计算该对象的哈希值码。

hashCode 是jdk 根据对象的地址或者字符串或者数字计算该对象的哈希码值的方法。

下列代码中用到 equals() 方法，因此需要重写 equals()，我们需要注意一个点：在重写 equals() 方法后必须对 hashcode() 方法进行重写。

public class newHashBucket<K, V>{
    static class Node<K, V> {
        private K key;
        private V value;
        private Node<K, V> next;
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    
    public Node<K, V>[] array = (Node<K, V>[])new Node[10];
    
    public int usedSize;
    
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    public newHashBucket() {
    }
    
    public void put(K key, V val) {
        Node<K, V> node = new Node<>(key, val);
        int hash = key.hashCode();
        int index = hash % array.length;

        Node<K,V> cur = array[index];

        while(cur != null) {
            if (cur.key.equals(key)) {
                cur.value = val;
                return;
            }
            cur = cur.next;
        }
        node.next = array[index];
        array[index] = node;

        usedSize ++;

        if(loadFactor() >= DEFAULT_LOAD_FACTOR) {
            resize();
        }
    }
    
    private float loadFactor() {
        return usedSize*1.0f / array.length;
    }
    
    private void resize () {
        Node[] tmpArray = new Node[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                Node curNext = cur.next;
                int hash = cur.key.hashCode();
                int index = hash % tmpArray.length;
                
                cur.next = tmpArray[index];
                tmpArray[index] = cur;
                
                cur = curNext;
            }
        }
        array = tmpArray;
    }
    
    public V getValue(K key) {
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K, V> cur = array[index];
        while (cur != null) {
            if (cur.key.equals(key)) {
                return cur.value;
            }
            cur = cur.next;
        }
        return null;
    }
}


//测试代码
class Person {
    public String id;

    public Person(String id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "Person{" +
                "id='" + id + '\'' +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(id, person.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

public class Testnew {
    public static void main(String[] args) {
        Person person1 = new Person("1");
        Person person2 = new Person("22");
        Person person3 = new Person("3");
        Person person4 = new Person("4");
        Person person5 = new Person("56");
        Person person6 = new Person("6");
        Person person7 = new Person("7");
        Person person8 = new Person("999");
        
        newHashBucket<Person, String> newHashBucket = new newHashBucket<>();
        
        newHashBucket.put(person1, "value1");
        newHashBucket.put(person2, "value2");
        newHashBucket.put(person3, "value3");
        newHashBucket.put(person4, "value4");
        newHashBucket.put(person5, "value5");
        newHashBucket.put(person6, "value6");
        newHashBucket.put(person7, "value7");
        newHashBucket.put(person8, "value8");
        
        System.out.println(newHashBucket.getValue(person1));	//value1
        System.out.println(newHashBucket.getValue(person2));	//value2
        System.out.println(newHashBucket.getValue(person3));	//value3
        System.out.println(newHashBucket.getValue(person4));	//value4
        System.out.println(newHashBucket.getValue(person5));	//value5
        System.out.println(newHashBucket.getValue(person6));	//value6
        System.out.println(newHashBucket.getValue(person7));	//value7
        System.out.println(newHashBucket.getValue(person8));	//value8
    }
}

OJ练习

138. 随机链表的复制

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;

        while (cur != null) {
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        } 

        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }
}

692. 前K个高频单词

import java.util.*;

class Solution {

    public static List<String> topKFrequent(String[] words, int k) {

        //1、计算每个单词出现的次数
        Map<String, Integer>  map = new HashMap<>();
        for (String s : words) {
            if(map.get(s) == null) {
                map.put(s, 1);
            } else {
                int val = map.get(s);
                map.put(s,val + 1);
            }
        }

        //2、已经统计完毕，创建小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String, Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) == 0) {
                    if (top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                } else {
                    if(top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }

        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String s = minHeap.poll().getKey();
            ret.add(s);
        }

        Collections.reverse(ret);
        return ret;
    }
}

旧键盘

import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNextLine()) {
            String str1 = scanner.nextLine();
            String str2 = scanner.nextLine();
            func(str1,str2);
        }

    }

    /**
     *
     * @param str1 : 期待输入的
     * @param str2 : 实际输入的
     */
    public static void func (String str1, String str2) {
        Set<Character> set = new HashSet<>();   // f n g 4 n

        for (char ch : str2.toUpperCase().toCharArray()) {
            set.add(ch);
        }

        Set<Character> setBroken = new HashSet<>();
        for (char ch : str1.toUpperCase().toCharArray()) {
            if(!set.contains(ch) && !setBroken.contains(ch)) {
                setBroken.add(ch);
                System.out.print(ch);
            }
        }
    }
}