Web全栈~24.数据结构(哈希)

迈不过友情╰ 2023-01-08 08:23 93阅读 0赞

# Web全栈~24.数据结构(哈希) #

## [上一期][Link 1] ##

## HashMap的原理 ##

底层结构是哈希表，采用了顺序表+链表结合结构；同一个链表的上所有元素的存储地址都是相同的，是发生冲突的元素

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70][]

链表上每个节点的就是一个Entry，字段包括四部分

![20200525175646442.png][]

哈希码可能不相同，存储地址相同。

### 哈希表的优点 ###

添加快、查询快（通过计算得到存储位置，不是通过比较） 无序 （key）唯一关键参数

默认主数组长度16； 默认装填因子0.75。 每次主数组扩容为原来的2倍 JDK8，当链表长度大于8，链表变成红黑树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70 1][]

第一步计算哈希码，不仅调用了hashCode()，有进行了多次散列。目的在于key不同，哈希码尽量不同，减少冲突

细节：发生冲突，经过比较不存在相同key的元素，要添加一个新的节点。不是加到链表最后，而是添加到链表最前

![20200525180130652.png][] ![20200525180149964.png][]

## 定义Map接口 ##

public interface Map { 
        //定义方法
        void put(Object key,Object value);
        Object get(Object key);
        int size();
        boolean isEmpty();
    	String toString();
    	
        //定义内部接口
        interface Entry{ 
            public Object getKey();
            public Object getValue();
        }
    }

## 接口的实现 ##

public class HashMap implements Map{ 
    
        private Node[] node;
        int size;
        public HashMap(int capacity){ 
            node = new Node[capacity];
        }
        public HashMap(){ 
            this(16);   //默认初始为16
        }
    
        //-------实现主要方法-------
    
        @Override
        public void put(Object key, Object value) { 
            //计算哈希码
            int hash = key.hashCode();
            //根据哈希码计算存储位置
            int index = hash % node.length;
            //如果放入数据的位置有数据
            if(node[index] != null){ 
                //键不重复
                Node current = node[index];
                while(current != null){ 
                    //如果键相同
                    if(current.key.equals(key)){ 
                        //覆盖值
                        current.value = value;
                        //因为键相同所以只是覆盖,并非新增,因此提前return
                        //防止后面size++导致数据错乱
                        return;
                    }
                    //遍历
                    current = current.next;
                }
                //创建新的节点
                Node newNode = new Node(hash,key,value);
                //让新的节点下一个为原来的节点
                newNode.next = node[index];
                //存储新的开始节点
                node[index] = newNode;
            }else{ 
                //放入数据的位置没有数据,直接放入
                node[index] = new Node(hash,key,value);
            }
            //如果没有发现相同的键,则长度增加
            size++;
        }
    
        @Override
        public Object get(Object key) { 
            //计算哈希码
            int hash = key.hashCode();
            //根据哈希码计算存储位置
            int index = hash % node.length;
            //查找对应的Entry
            Node entry = null;
            if (node[index] != null) { 
                Node currentEntry = node[index];
                while (currentEntry != null) { 
                    if (currentEntry.getKey().equals(key)) { 
                        entry = currentEntry;
                        break;
                    }
                    //向后移动链表
                    currentEntry = currentEntry.next;
                }
            }
            return entry == null ? null : entry.getValue();
        }
    
        @Override
        public String toString(){ 
            StringBuilder builder = new StringBuilder("{");
            for(int i=0;i<node.length;i++){ 
                if(node[i] != null){ 
                    Node entry = node[i];
                    while(entry != null){ 
                        builder.append(entry.getKey()+"="+entry.getValue()+",");
                        entry = entry.next;
                    }
                }
            }
            if(builder.length()!=1){ 
                //删除逗号
                builder.deleteCharAt(builder.length()-1);
            }
            builder.append("}");
            return builder.toString();
        }
    
        @Override
        public int size() { 
            return size;
        }
    
        @Override
        public boolean isEmpty() { 
            return size == 0;
        }
    
        //-------定义内部类实现Entry接口-------
        class Node implements Map.Entry{ 
            int hash;            //存储键的哈希码
            Object key;          //键
            Object value;        //值
            Node next;          //下一个节点
    
            @Override
            public Object getKey() { 
                return key;
            }
    
            @Override
            public Object getValue() { 
                return value;
            }
            //-------构造-------
            public Node() {  }
            public Node(int hash, Object key, Object value) { 
                this.hash = hash;
                this.key = key;
                this.value = value;
            }
            public Node(int hash, Object key, Object value, Node next) { 
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
            //-------toString-------
            public String toString() { 
                if (next != null) { 
                    return "{" + key + ":" + value + "-" + hash + " " + next + "}";
                } else { 
                    return "{" + key + ":" + value + "-" + hash + "}";
                }
            }
        }
    }

[Link 1]: https://blog.csdn.net/qq_41424688/article/details/112841553
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70]: /images/20221119/70d3d1e9833a4352a963b3c027a50c12.png
[20200525175646442.png]: /images/20221119/1f0efba1a7cd428a9c2cbd4493d68ace.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDI0Njg4_size_16_color_FFFFFF_t_70 1]: /images/20221119/88937acbc85a4330b95aca03d3dc0bcf.png
[20200525180130652.png]: https://img-blog.csdnimg.cn/20200525180130652.png
[20200525180149964.png]: /images/20221119/8c840fdf1147409394695b8c2772f7be.png