JavaSE---Map和Set

• 有一个英文词典，快速查找一个单词是否在词典中
• 快速查找某个名字在不在通讯录中

• 统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>
• 梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号

Map (Java Platform SE 8 ) (oracle.com)

 2.1 关于Map的说明

 Map.Entry （Java Platform SE 8 ） (oracle.com)

 注意：

 2.4 HashMap的使用案例

import java.util.TreeMap; 
import java.util.Map;
public static void TestMap()
{ 
    Map<String, String> m = new HashMap<>(); 
    // put(key, value):插入key-value的键值对 
    // 如果key不存在，会将key-value的键值对插入到map中,返回null 
    m.put("林冲", "豹子头"); 
    m.put("鲁智深", "花和尚"); 
    m.put("武松", "行者"); 
    m.put("宋江", "及时雨"); 
    String str = m.put("李逵", "黑旋风"); 
    System.out.println(m.size()); 
    System.out.println(m); 
    // put(key,value): 注意key不能为空，但是value可以为空 
    // key如果为空，会抛出空指针异常 
    //m.put(null, "花名"); 
    str = m.put("无名", null); 
    System.out.println(m.size()); 
    // put(key, value): 
    // 如果key存在，会使用value替换原来key所对应的value，返回旧value 
    str = m.put("李逵", "铁牛"); 
    // get(key): 返回key所对应的value
    // 如果key存在，返回key所对应的value 
    // 如果key不存在，返回null 
    System.out.println(m.get("鲁智深")); 
    System.out.println(m.get("史进")); 
    //GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值                 
    System.out.println(m.getOrDefault("李逵", "铁牛")); 
    System.out.println(m.getOrDefault("史进", "九纹龙")); 
    System.out.println(m.size());
    //containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN) 
    // 按照红黑树的性质来进行查找 
    // 找到返回true，否则返回false 
    System.out.println(m.containsKey("林冲")); 
    System.out.println(m.containsKey("史进")); 
    // containValue(value): 检测value是否包含在Map中，时间复杂度: O(N) 
    // 找到返回true，否则返回false 
    System.out.println(m.containsValue("豹子头")); 
    System.out.println(m.containsValue("九纹龙")); 
    // 打印所有的key 
    // keySet是将map中的key防止在Set中返回的 
    for(String s : m.keySet())
    { 
        System.out.print(s + " ")    
    }
    System.out.println(); 
    // 打印所有的value 
    // values()是将map中的value放在collect的一个集合中返回的 
    for(String s : m.values())
    { 
        System.out.print(s + " "); 
    }
    System.out.println(); 
    // 打印所有的键值对 
    // entrySet(): 将Map中的键值对放在Set中返回了 
    for(Map.Entry<String, String> entry : m.entrySet())
    { 
        System.out.println(entry.getKey() + "--->" + entry.getValue()); 
    }
    System.out.println(); 
}

 注意：

 3.2 HashSet的使用案例

import java.util.TreeSet; 
import java.util.Iterator; 
import java.util.Set;
public static void TestSet()
{ 
    Set<String> s = new HashSet<>(); 
    // add(key): 如果key不存在，则插入，返回ture 
    // 如果key存在，返回false
    boolean isIn = s.add("apple"); 
    s.add("orange"); 
    s.add("peach"); 
    s.add("banana"); 
    System.out.println(s.size()); 
    System.out.println(s); 
    isIn = s.add("apple"); 
    // add(key): key如果是空，抛出空指针异常
    //s.add(null); 
    // contains(key): 如果key存在，返回true，否则返回false         
    System.out.println(s.contains("apple")); 
    System.out.println(s.contains("watermelen")); 
    // remove(key): key存在，删除成功返回true 
    // key不存在，删除失败返回false 
    // key为空，抛出空指针异常 
    s.remove("apple"); 
    System.out.println(s); 
    s.remove("watermelen"); 
    System.out.println(s); 
    Iterator<String> it = s.iterator(); 
    while(it.hasNext())
    { 
        System.out.print(it.next() + " "); 
    }
    System.out.println(); 
}

692. 前K个高频单词 - 力扣（LeetCode）

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

 5.2 操作-查找

 5.3 操作-插入

2. 如果树不是空树，按照查找逻辑确定插入位置，插入新结点 

• cur 是 root，则 root = cur.right
• cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
• cur 不是 root，cur 是 parent.right，则 parent.right = cur.right

•  cur 是 root，则 root = cur.left
•  cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
•  cur 不是 root，cur 是 parent.right，则 parent.right = cur.left

•  需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题

public class BinarySearchTree 
{
public static class Node 
{ 
int key; 
Node left;
Node right;
public Node(int key) 
{ 
this.key = key; 
} 
}
private Node root = null; 
/**
* 在搜索树中查找 key，如果找到，返回 key 所在的结点，否则返回 null
* @param key
* @return
*/
public Node search(int key) 
{ 
Node cur = root; 
while (cur != null) 
{ 
if (key == cur.key) 
{ 
return cur; 
} 
else if (key < cur.key) 
{
cur = cur.left; 
} 
else 
{
cur = cur.right; 
} 
}
return null; 
}
/**
* 插入
* @param key
* @return true 表示插入成功, false 表示插入失败
*/
public boolean insert(int key) 
{ 
if (root == null) 
{ 
root = new Node(key); 
return true; 
}
Node cur = root; 
Node parent = null; 
while (cur != null) 
{ 
if (key == cur.key) 
{ 
return false; 
} 
else if (key < cur.key) 
{
parent = cur;
cur = cur.left; 
} 
else 
{
parent = cur;
cur = cur.right; 
} 
}
Node node = new Node(key); 
if (key < parent.key) 
{
parent.left = node; 
} 
else 
{
parent.right = node; 
}
return true; 
}
/**
* 删除成功返回 true，失败返回 false
* @param key
* @return
*/
public boolean remove(int key) 
{ 
Node cur = root; 
Node parent = null; 
while (cur != null) 
{ 
if (key == cur.key) 
{
break; 
} 
else if (key < cur.key) 
{
parent = cur;
cur = cur.left; 
} 
else 
{
parent = cur;
cur = cur.right; 
} 
}
// 该元素不在二叉搜索树中 
if(null == cur)
{
return false; 
}
/*
根据cur的孩子是否存在分四种情况 1. cur左右孩子均不存在 2. cur只有左孩子 3. cur只有右孩子 4. cur左右孩子均存在 看起来有四种情况，实际情况1可以与情况2或者3进行合并，只需要处理是那种情况即可 除了情况4之外，其他情况可以直接删除 情况4不能直接删除，需要在其子树中找一个替代节点进行删除
*/
// 请同学们根据上课掌握内容，完成删除的关键部分代码 
return true; 
} 
}

• 插入元素

• 搜索元素

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

负载因子和冲突率的关系粗略演示  

• 插入

        采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

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

// key-value 模型
public class HashBucket 
{
    private static class Node 
    {
        private int key;
        private int value; 
        Node next;
        public Node(int key, int value) 
        { 
            this.key = key; 
            this.value = value; 
        } 
    }
    private Node[] array;
    private int size; 
    // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75;
    public int put(int key, int value) 
    { 
        int index = key % array.length; 
        // 在链表中查找 key 所在的结点 
        // 如果找到了，更新 
        // 所有结点都不是 key，插入一个新的结点
        for (Node cur = array[index]; cur != null; cur = cur.next) 
        { 
            if (key == cur.key) 
            { 
                int oldValue = cur.value;
                cur.value = value; 
                return oldValue; 
            } 
        }
        Node node = new Node(key, value); 
        node.next = array[index]; 
        array[index] = node; 
        size++; 
        if (loadFactor() >= LOAD_FACTOR) 
        { 
            resize(); 
        }
        return -1; 
    }
    private void resize() 
    { 
        Node[] newArray = new Node[array.length * 2]; 
        for (int i = 0; i < array.length; i++) 
        { 
            Node next; 
            for (Node cur = array[i]; cur != null; cur = next) 
            { 
                next = cur.next; 
                int index = cur.key % newArray.length;
                cur.next = newArray[index]; 
                newArray[index] = cur; 
            } 
        }
        array = newArray; 
    }
    private double loadFactor() 
    { 
        return size * 1.0 / array.length; 
    }
    public HashBucket()
    { 
        array = new Node[8]; 
        size = 0; 
    }
    public int get(int key) 
    { 
        int index = key % array.length; 
        Node head = array[index]; 
        for (Node cur = head; cur != null; cur = cur.next) 
        { 
            if (key == cur.key) 
            { 
                return cur.value; 
            } 
        }
        return -1; 
    }
}

 6.11 性能分析