一、摘要

在集合系列的第一章，咱们了解到，Map 的实现类有 HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties等等。

应该有很多人不知道 IdentityHashMap 的存在，其中不乏工作很多年的 Java 开发者，本文主要从数据结构和算法层面，探讨 IdentityHashMap 的实现。

二、简介

IdentityHashMap 的数据结构很简单，底层实际就是一个 Object 数组，但是在存储上并没有使用链表来存储，而是将 K 和 V 都存放在 Object 数组上。

当添加元素的时候，会根据 Key 计算得到散列位置，如果发现该位置上已经有改元素，直接进行新值替换；如果没有，直接进行存放。当元素个数达到一定阈值时，Object 数组会自动进行扩容处理。

打开 IdentityHashMap 的源码，可以看到 IdentityHashMap 继承了AbstractMap 抽象类，实现了Map接口、可序列化接口、可克隆接口。

public class IdentityHashMap<K,V>     extends AbstractMap<K,V>     implements Map<K,V>, java.io.Serializable, Cloneable {     /**默认容量大小*/     private static final int DEFAULT_CAPACITY = 32;          /**最小容量*/     private static final int MINIMUM_CAPACITY = 4;          /**最大容量*/     private static final int MAXIMUM_CAPACITY = 1 << 29;          /**用于存储实际元素的表*/     transient Object[] table;          /**数组大小*/     int size;      /**对Map进行结构性修改的次数*/     transient int modCount;      /**key为null所对应的值*/     static final Object NULL_KEY = new Object();          ...... }

可以看到类的底层，使用了一个 Object 数组来存放元素；在对象初始化时，IdentityHashMap 容量大小为64；

public IdentityHashMap() {         //调用初始化方法         init(DEFAULT_CAPACITY); }

private void init(int initCapacity) {         //数组大小默认为初始化容量的2倍         table = new Object[2 * initCapacity]; }

三、常用方法介绍

3.1、put方法

put 方法是将指定的 key, value 对添加到 map 里。该方法首先会对map做一次查找，通过==判断是否存在key，如果有，则将旧value返回，将新value覆盖旧value；如果没有，直接插入，数组长度