HashMap常见面试题和源码注释（完整版在最后面）

怼烎@ 2022-12-08 05:21 95阅读 0赞

### 关于HashMap的几个面试题 ###

1.  ###### put数据时key与已有数据的hashCode相等时会怎么样？ ######
    
    答：产生hash碰撞，hash码相同，则通过key的`equals()`方法比较值是否相同.  
    key值不相等：则会在该节点的链表结构上新增一个节点（如果链表长度>=8且 数组节点数>=64 链表结构就会转换成红黑树）  
    key值相等：则用新的value替换旧的value
2.  ###### 什么时候会产生hash碰撞? 如何解决hash碰撞？ ######
    
    答：只要两个元素产生的hash值相同就会产生hash碰撞。  
    jdk8前采用`链表`解决hash碰撞、jdk8以后采用`链表 + 红黑树`解决hash碰撞。
3.  ###### 如果hashCode相同，如何存储key-value对? ######
    
    答：hashCode相同，进一步通过equals比较内容是否相同  
    相同：新值覆盖旧值  
    不相同：将新的key-value添加到HashMap中
4.  ###### hashMap是怎么扩容的？ ######
    
    答：通过put方法不断添加数据时，如果元素个数超过了阈值旧会触发扩容，默认情况是原来的2倍，并且将原来的数据复制过来
5.  ###### 如果确定了要存储的元素个数n，设置多少的初始容量可以减少扩容导致的性能损失？ ######
    
    答：应该设置初始容量`m= n / 0.75 + 1` 取整即可减少resize导致的性能损失。

### HashMap存储原理 ###

map以`key:value`的形式存储，而HashMap则是对`key`进行hash算法得到一个hash值，然后根据特定算法得到索引值

如果是直接new HashMap()初始容量为0,底层创建的是一个空数组
    添加第一个元素后会触发 扩容 达到默认初始容量16。

我们也都知道`HashMap`底层是`数组 + 链表 + 红黑树(jdk1.8以后)`

说起HashMap中的hash算法，是根据key的类型而定，key如果是String类型则会调用`String.hashCode()`返回一个hash值。

如果是自定义类 作为HashMap的key则必须重写`hashCode`方法和`Object.equals()`方法。  
否则会直接调用父类`Object.hashCode()`和`Object.equals()`方法，那么就不好达到我们想要的效果  
举个例子：使用下面这个类作为key

class Person{ 
    	private String name;
    	private Integer age;
    	Person(String name,Integer age){ 
    		this.name=name;
    		this.age=age;
    	}
    }

会产生如下问题：

1.  存的进去，取不出来
    
        HashMap hashMap = new HashMap<Person,String>();
        //存
        Person p1 = new Person("zhangsan",18);
        hashMap.put(p1,"职业：程序员");
        //取
        Person p2 = new Person("zhangsan",18);//想当然的创建一个对象
        //会得到null，因为此 Person 非 彼 Person。但我们希望得到 "职业：程序员"
        String info = hashMap.get(p2);
    
    会得到null（当然也有可能得到正确的数据，得碰运气），为什么呢？因为Person没有重写父类Object的`hashCode`和`equals`方法，那么HashMap就会调用Object的这两个方法进行存和取操作。`两次new就得到两个Person实例`两个不同得对象，他们得地址和hash值很显然不相同。因此存得进去，但不好取出来。

### 红黑树 ###

链表长度`>= 8`且Node数组长度`>= 64`，将链表转换为红黑树  
红黑树得查询效率是`log(n)`也因此才加入红黑树结构

### jdk1.8中的HashMap ###

HashMap的源码中有2k多行代码，如果粘贴出来会很长，不方便解读源码。

对HashMap进行简化和总结。最终将2k行代码尽量的缩成几十行的内容，方便理解。

### 初步的简化 ###

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { 
    
    	/* * 下面是成员属性的定义 */
        private static final long serialVersionUID = 362498820763181265L;  // 实现序列化接口的序列化默认版本号
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量等于16
        static final int MAXIMUM_CAPACITY = 1 << 30; // 2的30次方也等于 Integer.MAXVALUE
        static final float DEFAULT_LOAD_FACTOR = 0.75f;// 默认的扩容因子
        static final int TREEIFY_THRESHOLD = 8; // 红黑数的阈值，hash碰撞达到了8链表才会转换成红黑数
        static final int UNTREEIFY_THRESHOLD = 6;// hash碰撞小于6才解开红黑树结构转换成链表结构
        static final int MIN_TREEIFY_CAPACITY = 64; // 树型容量的最小值，这个值不能小于 4*TREEIFY_THRESHOLD = 32
        transient Node<K,V>[] table;// 真正存储数据的数组结构
        transient Set<Map.Entry<K,V>> entrySet;// 所有节点Entry的集合
        transient int size;// hashMap的大小
        transient int modCount;// 并发修改计数，用于检测并发修改异常的值
        int threshold;// 扩容的条件，threshold=0.75*容量
        final float loadFactor;// 加载因子，默认值为0.75.可以通过构造方法重新设定
        
       /** * * 下面的是静态内部类，可以粗略的过一眼，不用细究代码。 * */
        // 这个结构很重要，是真正存储数据的数据结构
        static class Node<K,V> implements Map.Entry<K,V> { 
            final int hash; // 存储的 hash值
            final K key;    // 存储的 key值
            V value;        // 存储的 value值
            Node<K,V> next; // 链表结构，下一个节点的数据。结合前面定义的 transient Node<K,V>[] table;因此说HashMap的存储结构是数组+链表。
            
            Node(int hash, K key, V value, Node<K,V> next) { } // 构造方法
            
            public final K getKey() { }        // 获取当前节点的key
            public final V getValue() { }      // 获取当前节点的value
            public final String toString() { } // 返回{key:value}的字符串
            public final int hashCode() { }    // hash当前节点的key，value并返回hash值
            public final V setValue(V newValue) { }	// 给节点设置value值
            public final boolean equals(Object o) { }// 实现equals方法用于比较o与当前节点是否相等
        }
    
    	/* * 树节点数据结构，重要部分 */
        static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 
            TreeNode<K,V> parent;	// 父节点
            TreeNode<K,V> left;		// 左节点
            TreeNode<K,V> right;	// 右节点
            TreeNode<K,V> prev;		// 删除后需要取消链接
            boolean red;			// 用来判断当前节点是红还是黑节点
            /* 构造方法，创建对象的时候数据也存进来了 */
            TreeNode(int hash, K key, V val, Node<K,V> next) { }
           
            // 查找节点
            final TreeNode<K,V> find(int h, Object k, Class<?> kc) { }
            // 获取红黑树中的节点
            final TreeNode<K,V> getTreeNode(int h, Object k) { }
    
            // 链表 转换成 红黑树
            final void treeify(Node<K,V>[] tab) { }
            // 红黑树 转换成 链表
            final Node<K,V> untreeify(HashMap<K,V> map) { }
            
            // 添加红黑树节点
            final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) { }
            // 删除红黑树节点
            final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,boolean movable) { }// 移除节点
            final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { } // 拆分
            // 左旋
            static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,TreeNode<K,V> p) { }
            // 右旋
            static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,TreeNode<K,V> p) { }
            // 插入元素时保存平衡
            static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) { }
            // 删除元素时保存平衡
            static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,TreeNode<K,V> x) { }
            final TreeNode<K,V> root() { }
            static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { }
            static int tieBreakOrder(Object a, Object b) { }
            static <K,V> boolean checkInvariants(TreeNode<K,V> t) { }
        }
    	static Class<?> comparableClassFor(Object x) { /*省略*/} //
    	//Entry集合的内部结构，其目的就是实现Set方法，方便获取Set中的Entry（实际存储的数据结构）
        final class EntrySet extends AbstractSet<Map.Entry<K,V>> { 
            public final int size(){ }   // Set中元素个数
            public final void clear(){ } // 清空Set
            public final Iterator<Map.Entry<K,V>> iterator() { } // 迭代器，迭代获取Set内容
            public final boolean contains(Object o) { } // 是否包含某个元素
            public final boolean remove(Object o) { }   // 移除某个元素
            public final Spliterator<Map.Entry<K,V>> spliterator() { } // 拆分Set集合，暂没有遇到使用场景。跳过
            public final void forEach(Consumer<? super Map.Entry<K,V>> action) { } // 遍历元素，使用函数式接口Consumer，可以使用lambda表达式进行遍历消费
        }
       /* * 下面是类迭代器分别代表hash、key、value、Entry */
        abstract class HashIterator { 
            Node<K,V> next;        // 下一个节点
            Node<K,V> current;     // 当前节点
            int expectedModCount;  // 预期的修改计数
            int index;             // 当前索引值
            HashIterator() { } //构造方法
            public final boolean hasNext() { } // 判断是否还有下一个Node节点
            final Node<K,V> nextNode() { }     // 返回下一个节点Node
            public final void remove() { }     // 移除当前节点
        }
        final class KeyIterator extends HashIterator implements Iterator<K> { public final K next() {   }// 返回下一个节点的 键 key}
        final class ValueIterator extends HashIterator implements Iterator<V> {  public final V next() {  }//返回下一个节点的 值 value}
        final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>> { public final Map.Entry<K,V> next() {  }//返回下一个节点}
        /* * 下面是Spliterator和上面迭代器一样作用， * 只不是这些迭代器可以并行处理 * */
        static class HashMapSpliterator<K,V> { 
            final HashMap<K,V> map;
            Node<K,V> current;          // 当前节点
            int index;                  // 当前索引
            int fence;                  // 上一个节点索引
            int est;                    // 预估值
            int expectedModCount;       // 预期的并发修改次数
            //构造方法
            HashMapSpliterator(HashMap<K,V> m, int origin,int fence, int est,int expectedModCount) { }
            final int getFence() { }//返回上一个节点的索引
            public final long estimateSize() { } // 返回Map的预估个数
        }
    	// 该类的目的是解决hashMap存储数据过大，不方便处理，对数据进行拆分，提供性能。
        static final class KeySpliterator<K,V> extends HashMapSpliterator<K,V> implements Spliterator<K> { 
    		// 构造方法
    		KeySpliterator(HashMap<K,V> m, int origin, int fence, int est, int expectedModCount) { }
            public KeySpliterator<K,V> trySplit() { } // 
            public void forEachRemaining(Consumer<? super K> action) { }//遍历剩余元素
            /*如果有剩余元素，执行Consumer操作，并返回true，否则返回false */
            public boolean tryAdvance(Consumer<? super K> action) { } 
            public int characteristics() { } //特征值
        }
        static final class ValueSpliterator<K,V> extends HashMapSpliterator<K,V> implements Spliterator<V> { 
        	// 
            ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est,int expectedModCount) { } 
            public ValueSpliterator<K,V> trySplit() { }
            public void forEachRemaining(Consumer<? super V> action) { }
            public boolean tryAdvance(Consumer<? super V> action) { }
            public int characteristics() { }
        }
        static final class EntrySpliterator<K,V> extends HashMapSpliterator<K,V> implements Spliterator<Map.Entry<K,V>> { 
            public EntrySpliterator<K,V> trySplit() { }
            public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) { }
            public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) { }
            public int characteristics() { }
        }
        
        
        /* * 四种构造方法 */
        public HashMap(int initialCapacity, float loadFactor) { }
        public HashMap(int initialCapacity) { }
        public HashMap() { }
        public HashMap(Map<? extends K, ? extends V> m) { }
    
    	/* * HashMap中定义的方法 */
    	static final int tableSizeFor(int cap) { } // 得到大于cap的最佳容量值
    	final float loadFactor() { }	// 返回加载因子
    	final int capacity() { }		// 返回容量值
        public void clear() { }		// 清空hashMap
        public int size() { }		// 返回hashMap存储了多少个元素
        public boolean isEmpty() { }	// 判断hashMap是否没有存储元素
        static final int hash(Object key) { }	// 得到key的hash值
        /* 添加和修改 */
        public V put(K key, V value) { }			// 存除键值对数据
        // 实际真正存数据的方法put方法就是调用它才真正的将key，value存入hashMap
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { }
        public void putAll(Map<? extends K, ? extends V> m) { }	//批量添加
        // 查询
        public V get(Object key) { }		// 根据key取出hashMap中的内容
        // 删除
        public V remove(Object key) { }	// 删除key所对于的键值对
    	// hashMap的扩容方法
        final Node<K,V>[] resize() { }	
        public boolean containsKey(Object key) { }		// 判断hashMap中是否包含key
        public boolean containsValue(Object value) { }	// 判断hashMap中是否包含value
        final void treeifyBin(Node<K,V>[] tab, int hash) { }// 转换成红黑树
        //获取节点
        final Node<K,V> getNode(int hash, Object key) { }
        //删除节点
        final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) { }
    	// 批量添加Entry
        final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { }
        public Collection<V> values() { } // 获取所有value
        
        public Set<K> keySet() { }
        final class KeySet extends AbstractSet<K> { }
        final class Values extends AbstractCollection<V> { }
        public Set<Map.Entry<K,V>> entrySet() { }
    
    	/* * 下面是集合类作者失误导致的结果， * 不用细究， * 原因是HashMap实现了Map接口，继承的AbstractMap也实现了同样的接口 * 导致出现下面这么多重写方法。（后作者发现自己的错误，想修改，但被拒绝了，因为jdk组织认为不值得修改） */
    	@SuppressWarnings({ "rawtypes","unchecked"})
        static int compareComparables(Class<?> kc, Object k, Object x) { }
        @Override
        public V getOrDefault(Object key, V defaultValue) { }
        @Override
        public V putIfAbsent(K key, V value) { }
        @Override
        public boolean remove(Object key, Object value) { }
        @Override
        public boolean replace(K key, V oldValue, V newValue) { }
        @Override
        public V replace(K key, V value) { }
        @Override
        public V computeIfAbsent(K key,Function<? super K, ? extends V> mappingFunction) { }
        public V computeIfPresent(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction) { }
        @Override
        public V compute(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction) { }
        @Override
        public V merge(K key, V value,BiFunction<? super V, ? super V, ? extends V> remappingFunction) { }
        @Override
        public void forEach(BiConsumer<? super K, ? super V> action) { }
        @Override
        public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { }
        @SuppressWarnings("unchecked")
        @Override
        public Object clone() { }
        private void writeObject(java.io.ObjectOutputStream s)}
        private void readObject(java.io.ObjectInputStream s)throws IOException, ClassNotFoundException { }
        Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { }
        Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) { }
        TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { }
        TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { }
        void reinitialize() { }
        void afterNodeAccess(Node<K,V> p) {  }
        void afterNodeInsertion(boolean evict) {  }
        void afterNodeRemoval(Node<K,V> p) {  }
        void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException { }
    
    
    }

### 再度简化HashMap ###

### 最终的简化 ###

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { 
    	/* * 成员属性的定义 * 初始容量16、 * 扩容因子0.75、 * 实际存储数据的Node数组， * 链表转红黑树长度阈值8、 * 保持红黑树结构的阈值6 */
    	
    	/* * 静态内部类的定义，例如：红黑树节点、节点 * */
    	
    	/* * HashMap中定义的方法 * put、get、putVal、remove、clear等常用方法 * */
    	
    
    }