devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

01-手撕HashMap

作者：凡人多烦事01 | 2024-03-27 15:45:10

赞

踩

01-手撕HashMap

Java集合 01-手撕HashMap

1. 为什么需要HashMap?

1）存储键值对：

keyvalue
电脑$1600
手机$12
导管$1

2）查询效率要求高：O(1)级别，快速查询，空间换取时间。

2. 设计存储key-vaalue的基本数据结构

题目1 key-value数据结构（手撕代码）

数据结构的两个基本基础单元为：数组和链表，分别以数组和链表为基础，设计存储key-value的数据结构。（键值对：String-Integer，完成put和get方法）

1）数组

// 数组构建 三个方法：1.get() 2.put() 3.resize()
public class KeyValue {
    private Node[] table;
    private int size = 0;
    private int capacity = 0;
    final private int DEFAULT_INITIAL_CAPACITY= 16;

    public KeyValue(){
        capacity = DEFAULT_INITIAL_CAPACITY;
        table = new Node[capacity];
    }
    //1.查找元素
    public Integer get(String key) {
        for (int i = 0; i < size; i++) {
            if (table[i].key.equals(key)) {
                return table[i].value;
            }
        }
        return null;
    }
    
    //2.添加元素
    public Integer put(String key,Integer value){
        //查找key是否已存在,存在则替换
        for (int i = 0; i < size; i++) {
            if(table[i].key.equals(key)){
                table[i].value = value;
                return value;
            }
        }
        size ++;
        if (size > capacity) resize();
        table[size] = new Node(key, value);
        return value;
    }

    //3.扩容
    private void resize(){
        capacity <<= 1;
        Node[] newTable = new Node[capacity];
        for (int i = 0;i < table.length;i++){
            newTable[i] = table[i];
        }
        table = newTable;
    }

    //存储单元
    class Node{
        String key;
        Integer value;
        public Node(String key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }

}

  • 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

2）链表

//链表构建 2个方法：1.get() 2.put()
public class KeyValue {
    private LinkedList<Node> table;
    private int size = 0;
    public KeyValue(){
        table = new LinkedList<Node>();
    }
    
    //1.查找元素
    public Integer get(String key) {
        for (int i = 0; i < table.size(); i++) {
            Node temp = table.get(i);
            if(temp.key.equals(key)){return temp.value;}
        }
        return null;
    }

    //2.添加元素
    public Integer put(String key,Integer value){
        //查找key是否已存在,存在则替换
        for (int i = 0; i < table.size(); i++) {
            Node temp = table.get(i);
            if(temp.key.equals(key)){
                temp.value = value;
                return value;
            }
        }
        size ++;
        Node newNode = new Node(key, value);
        table.add(newNode);
        return value;
    }
    
    //存储单元
    class Node{
        String key;
        Integer value;
        public Node(String key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }

}

  • 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

3）如何提高查询效率

*数组链表
查询O(n)O(n)
添加O(n)O(n)
扩容创建新的数组（慢）链表添加（快）

Key-value的核心在于查询效率，而数组的内存为连续空间，因此查询上数组优于链表；添加操作上链表效率比数组高。

链表无法完成O(1)的查询操作，只有通过array[i]，通过数组下标查询才能实现O(1)的查询效率。

问题1：如何接近O(1)的查询效率？

思路：尽量让每一个key对应一个数组下标。

  1. 新建数组table[] ,计算每一个key的hash值；
  2. hash值对table.length取余得到key在数组的位置index；
  3. 在table[index]放入key-value。

问题2：不同key得到的index重复怎么解决？

思路：相同index的key都放在table[index]，尽量减少index一致的情况（hash冲突）

  1. table[index] 存放的对象为链表，链表存储的为key-value值中index一致的元素；
  2. 优化hash函数
  3. 合适的扩容机制

题目2: 接近O(1)查询 (手撕代码）

数组形式的key-value（String-Integer）数据结构，实现接近O(1)的查询。（key-value数据小于64个）**

//三个方法：1.get() 2.put() 3.hash()
public class KeyValue {
    private Node[] table;
    private int size = 0;
    private int capacity = 0;
    final private int DEFAULT_INITIAL_CAPACITY= 16;

    public KeyValue(){
        capacity = DEFAULT_INITIAL_CAPACITY;
        table = new Node[capacity];
    }
    //1.查找元素
    public Integer get(String key) {
        //计算key的hash值，得到index
        int hash = hash(key);
        int index = hash % capacity;
        Node node = table[index];
        while (node != null){
            if(node.key.equals(key)){return node.value;}
            node = node.next;
        }
        return null;
    }

    //2.添加元素
    public Integer put(String key,Integer value){
        //计算key的hash值，得到index
        int hash = hash(key);
        int index = hash % capacity;
        //hash桶不存在则添加
        Node node = table[index];
        if (node == null) {
            table[index] = new Node(key,value);
            return value;
        }
        //存在则查询，判断更新或者添加
        while (node.next != null){
            if(node.key.equals(key)){
                node.value = value;
                return value;
            }
            node = node.next;
        }
        //不存在则添加 node.next =null;尾插法
        node.next = new Node(key, value);
        return value;
    }

    //3.hash函数（HashMap源码）
    private int hash(String key){
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//高位也参与hash值
    }

    //存储单元
    class Node{
        int hash;
        String key;
        Integer value;
        Node next;
        public Node(String key, Integer value) {
            this.key = key;
            this.value = value;
            this.hash = hash(key);
        }
    }

}

  • 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

优化：

  1. 计算table[index] :
 int index = hash % table.length;
 //优化  table.length 始终为2的n次方
 int index = hash &(table.length - 1)

  • 1
  • 2
  • 3
  1. 适当扩容，使得HashMap更散列

3.空间与查询兼并：扩容机制

HashMap的难点与核心为扩容机制。

4.红黑树进一步提高查询效率

  1. 当size大于64，同时链表长度大于8时，哈希桶的链表变为红黑树。
  2. 红黑树的节点数小于6时，哈希桶的红黑树退化为链表。
  3. 为什么不用AVL树 or B+树？为什么HashMap使用红黑树而不是AVL树或者B+树.

5.常见面试题。

HashMap面试题汇总.

  1. HashMap的底层数据结构
  2. HashMap 的长度为什么是2的幂次方？
  3. HashMap的put过程.
  4. HashMap数组resize过程
  5. 红黑树的5个特点
  6. 头插法和尾插法

6.HashMap的缺点

线程不安全。

题目3 请实现Hashmap的线程不安全情况（手撕代码）

请实现HashMap中线程不安全的情况。

//账户有10000块，两个人去消费，每次1000
public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> account = new HashMap<>();
        //账户充值10000元
        account.put("money",10000);
        //两个人共享账户
        Thread threadA = new Thread(new ThreadA(account));
        Thread threadB = new Thread(new ThreadA(account));
        threadA.start();
        threadB.start();
        try {
            threadA.join();
            threadB.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("余额:" + account.get("money"));
    }
}

class ThreadA implements Runnable{
    HashMap<String, Integer> map = null;
    public ThreadA(HashMap<String, Integer> map) {
        this.map = map;
    }
    @Override
    public void run() {
        for (int i = 1; i <= 10; i++) {
            try {
                Thread.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            if(map.get("money") > 0){
                map.replace("money",map.get("money") - 1000);
                System.out.println(Thread.currentThread().getName()+" 消费: "+ i*1000);
            }
        }
    }
}

  • 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

结果两个人消费12000，账户初始金额10000，线程不安全。

如何解决，请看ConcurrenHashMap。

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/325210
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号