重写hashmap源码

❶ java集合：关于hashmap存储一个对象，中间改变对象的值，为什么再remove不能用新名字来删除

这个得看hashset的源码了，内部会以hashcode或其经过某种算法得到的二次hash值为key来组织存储数据。

你重写了book的hashcode方法，并且内部用到了name来计算hashcode,那么当你修改了name后，它的hashcode自然变了，那么它就在原来的hashset里找不到了，自然删除不掉。

❷ 作为一个面试官，我会问初级java工程师哪些问题

初级java工程师多数是刚毕业或者工作1,2年的新人。对于新人，面试中基础问题会问道很多，因为先要考察这个人的基础。

关于基础类的题目，我在面试初级java工程师的时候一般会问下面两大类问题，每类5个题目，这样下来我就基本可以了解这位工程师的程度了。

java基础类

面向对象基础类

最后，如果前面问题回答的不错，会补充两个编程习惯问题。

1.在你写过的代码中，你写过超过2层的循环吗，怎么实现的？

回答：没有，就算ok；如果回答有，听一下实现，如果原因说不出来，扣分。

2.在你写过的代码中，if语句最多嵌套了几层，最多有多少分支，怎么实现的？

回答：3层以下，就算ok；如果回答3层以上，听一下实现，如果原因说不出来，扣分。

4，5个分支，就算ok；如果回答5个分支以上，听一下实现，如果原因说不出来，扣分。

最后两个题其实比较陷阱，但是正是一个反向的思考才能了解面试者之前的工作状态。

如果面试者在平日里就有好的习惯，自然不用担心。

❸ HashMap是什么东西

HashMap，中文名哈希映射，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。HashMap数组每一个元素的初始值都是Null。

HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了异步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

(3)重写hashmap源码扩展阅读：

因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。

HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可。

❹ HashMap源码分析

HashMap（jdk 1.8）
  使用哈希表存储键值对，底层是一个存储Node的table数组。其基本的运行逻辑是，table数组的每一个元素是一个槽，用于存储Node对象，向Hash表中插入键值对时，首先计算键的hash值，并对数组容量（即数组长度）取余，定位该键值对应放在哪个槽中，若槽中已经存在元素（即哈希冲突），将Node节点插入到冲突链表尾端，当该槽中结点超过一定数量（默认为8）并且哈希表容量超过一定值（默认为64）时，对该链表进行树化。低于一定数量（默认为6）后进行resize时，树形结构又会链表化。当哈希表的总节点数超过阈值时，对哈希表进行扩容，容量翻倍。

由于哈希表需要用到key的哈希函数，因此对于自定义类作为key使用哈希表时，需要重写哈希函数，保证相等的key哈希值相同。

由于扩容或树化过程Node节点的位置会发生改变，因此哈希表是无序的，不同时期遍历同一张哈希表，得到的节点顺序会不同。

成员变量

    Hash表的成员变量主要有存储键值对的table数组，size，装载因子loadFactory，阈值theshold，容量capacity。

table数组：

哈希表的实质就是table数组，它用来存储键值对。哈希表中内部定义了Node类来封装键值对。

 Node类实现了Map的Entry接口。包括key，value，下一个Node指针和key的hash值。

 容量Capacity：

HashMap中没有专门的属性存储容量，容量等于table.lenth，即数组的长度，默认初始化容量为16。初始化时，可以指定哈希表容量，但容量必须是2的整数次幂，在初始化过程中，会调用tableSizeFor函数，得到一个不小于指定容量的2的整数次幂，暂时存入到threshold中。

注意，若容量设置过大，那么遍历整个哈希表需要耗费更多的时间。

    阈值threshold：

指定当前hash表最多存储多少个键值对，当size超过阈值时，hash表进行扩容，扩容后容量翻倍。

   loadFactory：

threshold=capacity*loadFactory。

装填因子的大小决定了哈希表存储键值对数量的能力，它直接影响哈希表的查找性能。初始化时可以指定loadFactory的值，默认为0.75。

 初始化过程

哈希表有3个构造函数，用户可以指定哈希表的初始容量和装填因子，但初始化过程只是简单填入这两个参数，table数组并没有初始化。注意，这里的initialCapacity会向上取2的整数次幂并暂时保存到threshold中。

table数组的初始化是在第一次插入键值对时触发，实际在resize函数中进行初始化。

hash过程与下标计算

哈希表是通过key的哈希值决定Node放入哪个槽中， 在java8中 ，hash表没有直接用key的哈希值，而是自定义了hash函数。

哈希表中的key可以为null，若为null，哈希值为0，否则哈希值（一共32位）的高16位不变，低16位与高16位进行异或操作，得到新的哈希值。（h >>> 16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。）

之所以这样处理，是与table的下标计算有关

因为，table的长度都是2的幂，因此index仅与hash值的低n位有关（n-1为0000011111的形式），hash值的高位都被与操作置为0了，相当于hash值对n取余。

由于index仅与hash值的低n位有关，把哈希值的低16位与高16位进行异或处理，可以让Node节点能更随机均匀得放入哈希表中。

get函数：

V  get(Object key) 通过给定的key查找value

先计算key的哈希值，找到对应的槽，遍历该槽中所有结点，如果结点中的key与查找的key相同或相等，则返回value值，否则返回null。

注意，如果返回值是null，并不一定是没有这种KV映射，也有可能是该key映射的值value是null，即key-null的映射。也就是说，使用get方法并不能判断这个key是否存在，只能通过containsKey方法来实现。

put函数

V put(K key, V value) 存放键值对

计算key的哈希值，找到哈希表中对应的槽，遍历该链表，如果发现已经存在包含该key的Node，则把新的value放入该结点中，返回该结点的旧value值（旧value可能是null），如果没有找到，则创建新结点插入到 链表尾端 （java7使用的是头插法），返回null。插入结点后需要判断该链表是否需要树化，并且判断整个哈希表是否需要扩容。

由该算法可以看出，哈希表中不会有两个key相同的键值对。

resize函数

    resize函数用来初始化或扩容table数组。主要做了两件事。

1.根据table数组是否为空判断初始化还是扩容，计算出相应的newCap和newThr，新建table数组并设置新的threshold。

2.若是进行扩容，则需要将原数组中的Node移植到新的数组中。

由于数组扩容，原来键值对可能存储在新数组不同的槽中。但由于键值对位置是对数组容量取余（index=hash(key)&(Capacity-1)）,由于Capacity固定为2的整数次幂，并新的Capacity（newCap）是旧的两倍（oldCap）。因此，只需要判断每个Node中的hash值在oldCap二进制那一位上是否为0(hash&oldCap==0)，若为0，对newCap取余值与oldCap相同，Node在新数组中槽的位置不变，若为1，新的位置是就得位置加一个oldCap值。

因此hashMap的移植算法是，遍历旧的槽：

若槽为空，跳过。

若槽只有一个Node，计算该Node在新数组中的位置，放入新槽中。

若槽是一个链表，则遍历这个链表，分别用loHead，loTail,hiHead,hiTail两组指针建立两个链表，把hash值oldCap位为0的Node节点放入lo链表中，hash值oldCap位为1的节点放入hi链表中，之后将两个链表分别插入到新数组中，实现原键值对的移植。

lo链表放入新数组原来位置，hi链表放入新数组原来位置+oldCap中

树化过程 ：

当一个槽中结点过多时，哈希表会将链表转换为红黑树，此处挖个坑。

[总结] java8中hashMap的实现原理与7之间的区别：

1.hash值的计算方法不同 2.链表采用尾插法，之前是头插法 3.加入了红黑树结构

❺ 如何阅读concurrenthashmap源码

nized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的不同部分进行的修改。ConcurrentHashMap内部使用段(Segment)来表示这些不同的..

❻ HashMap底层实现原理剖析

Hashmap是一种非常常用的、应用广泛的数据类型，最近研究到相关的内容，就正好复习一下。网上关于hashmap的文章很多，但到底是自己学习的总结，就发出来跟大家一起分享，一起讨论。

1.HashMap的数据结构：在java 中 数据结构，最基本 也就两种 一种数组 一种模拟指针。所有的数据结构都可以用这两个基本结构来构造的，hashmap也不例外。Hashmap实际上是一个数组和链表的结合体。数组的默认长度为16，

2.hashMap源码解析

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始化容量大小 

static final int MAXIMUM_CAPACITY = 1 << 30; ///容器最大值

static final float DEFAULT_LOAD_FACTOR = 0.75f; //加载影子

static final Entry[] EMPTY_TABLE = {}; //null 的hashMap

transient Entry[] table = (Entry[]) EMPTY_TABLE;///动态扩大容器时使用的一个hashMap

transient int size;//当前数据量

int threshold;//扩大容器时的大小 为 capacity * load factor

final float loadFactor;//使用率阀值，默认为：DEFAULT_LOAD_FACTOR

存取元素 ：调用put方法

public V put(K key, V value) { 

//判断当前table 为Null 第一次Put 

 if (table == EMPTY_TABLE) {

     inflateTable(threshold);  //初始化容器的大小

 }

 if (key == null) 

 return putForNullKey(value); //判断当前key 为null 将Null key添加到数组的第一个位置

 int hash = hash(key); //将当前key进行hash 详情见下方

 int i = indexFor(hash, table.length); //调用完hash算法后，详情见下方

 for (Entry e = table[i]; e != null; e = e.next) { //循环判断当前数组下标为Entry的实体 将当前key相同的替换为最新的值

            Object k;

            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

                V oldValue = e.value;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

            }

        }

        modCount++;

        addEntry(hash, key, value, i); //如果key都不同 则添加Entry.详情见下方

        return null;

    }

hashMap的hash算法剖析

final int hash(Object k) {

        int h = hashSeed;

        if (0 != h && k instanceof String) {  //判断当前k是否为string 和

            return sun.misc.Hashing.stringHash32((String) k); //使用stringHash32算法得出key   的hash值

        }

        h ^= k.hashCode(); //调用key的hashCode 得出值 后使用"或"运算符 

        h ^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^ (h >>> 4);

前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的 元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大优化了查询的效率。

一个十进制数32768(二进制1000 0000 0000 0000)，经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗？或许这样还看不出什么，再举个数字61440(二进制1111 0000 0000 0000)，运算结果是65263(二进制1111 1110 1110 1111)，现在应该很明显了，它的目的是让“1”变的均匀一点，散列的本意就是要尽量均匀分布。使用上述算法后 "1"就变得很均匀了。

我们用table[index]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素（这个元素是HashMap内部定义的一个类Entity， 基本结构它包含三个类，key，value和指向下一个Entity的next）,没有的话就创建一个Entity对象，在 table[index]位置上插入，这样插入结束；如果有的话，通过链表的遍历方式去逐个遍历，看看有没有已经存在的key，有的话用新的value替 换老的value；如果没有，则在table[index]插入该Entity，把原来在table[index]位置上的Entity赋值给新的 Entity的next，这样插入结束

    }

indexFor 返回当前数组下标 ，

static int indexFor(int h, int length) {

        return h & (length-1);

    }

那么得到key 之后的hash如何得到数组下标呢 ？把h与HashMap的承载量（HashMap的默认承载量length是16，可以自动变长。在构造HashMap的时候也可以指定一个长 度。这个承载量就是上图所描述的数组的长度。）进行逻辑与运算，即 h & (length-1)，这样得到的结果就是一个比length小的正数，我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的 位置。第2步那个算法的意义就是希望能够得出均匀的index，这是HashTable的改进，HashTable中的算法只是把key的 hashcode与length相除取余，即hash % length，这样有可能会造成index分布不均匀。

首先来解释一下为什么数组大小为2的幂时hashmap访问的性能最高？

看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！ 

void addEntry(int hash, K key, V value, int bucketIndex) {

  //// 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小

        if ((size >= threshold) && (null != table[bucketIndex])) {

            resize(2 * table.length);

            hash = (null != key) ? hash(key) : 0;

          //// 设置“bucketIndex”位置的元素为“新Entry”，// 设置“e”为“新Entry的下一个节点”

            bucketIndex = indexFor(hash, table.length);

        }

        createEntry(hash, key, value, bucketIndex);

    }

//将当前key 和value添加到Entry[]中

void createEntry(int hash, K key, V value, int bucketIndex) { 

        Entry e = table[bucketIndex];  //将第一个就得table 复制个新的entry 

        table[bucketIndex] = new Entry<>(hash, key, value, e); //将当前新的Entry 复制个table[bucketIndex]  旧的table[bucketIndex] 和新的table[buckIndex]之间用next关联。第一个键值对A进来，通过计算其key的hash得到的index=0，记做:table[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做: B.next = A ,table[0] = B,如果又进来C,index也等于0,那么 C.next = B ,table[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起

        size++; //容量加1

    }

以上就是HashMap添加元素时的过程解析

那么如何get元素呢？

public V get(Object key) {

 if (key == null) return getForNullKey(); //当前key是否为null 如果为null值返回table[0]这个value

    Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();

    }

final EntrygetEntry(Object key) {

 if (size == 0) { return null; }  //判断容量是否大于0 

 int hash = (key == null) ? 0 : hash(key); //对当前key 进行hash hash后得到一个值

 for (Entry e = table[indexFor(hash, table.length)]; //获取当前Entry 循环遍历

            e != null;

            e = e.next) {

            Object k;

            if (e.hash == hash &&

                ((k = e.key) == key || (key != null && key.equals(k))))

                return e;

        }

        return null;

    }

扩展问题:

1.当前我们的hashMap中越来越大的之后，"碰撞"就越来越明显，那么如何解决碰撞呢？扩容！

当hashmap中的元素个数超过数组大小capti*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过上面annegu已经说过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题

HashMap的两种遍历方式

第一种

Map map = newHashMap();

Iterator iter = map.entrySet().iterator();

while(iter.hasNext()) {

Map.Entry entry = (Map.Entry) iter.next();

Object key = entry.getKey();

Object val = entry.getValue();

}

效率高,以后一定要使用此种方式！

第二种

Map map = newHashMap();

Iterator iter = map.keySet().iterator();

while(iter.hasNext()) {

Object key = iter.next();

Object val = map.get(key);

}

效率低,以后尽量少使用！

归纳

简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，

也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

❼ 为什么要重写hashcode方法

重载equals比说基于象内容实现保留hashCode实现变能某两象明明相等hashCode却
用其作键保存hashMap、hasoTable或hashSet再相等找另作键值查找候则根本找
使用HashMapkey自定义类必须重写hashcode()equals()
于每象通其hashCode()其整形值（散列码）该整型值处理作数组标存放该象所应Entry（存放该象及其应值） equals()则HashMap插入值或查询使用HashMap插入值或查询值应散列码与数组散列码相等则通equals比较key值否相等所想自建象作HashMapkey必须重写该象继承objecthashCodeequals 2.本hashcode()equals()干嘛要重写直接用原行 HashMap要比较key否相等要同使用两函数自定义类hashcode()继承于Object类其hashcode码默认内存址即便相同含义两象比较相等例两羊象理解两象应该相等重写 hashcode（）比较相等
HashMap比较key先求keyhashcode(),比较其值否相等若相等再比较equals(),若相等则认相等若equals()相等则认相等重写hashcode()重写equals()比较equals()看否同象（即进行内存址比较）,所必定要两起重写HashMap用判断key否相等其实调用HashSet判断加入元素否相等
引用别说段哈~
般说要类象放入容器通要其重写equals()让比较址值内容值特别要类象放入散列要重写hashCode()；要放序容器要重写compareTo()
equals()相等两象hashcode()定相等；
equals（）相等两象却并能证明hashcode()相等换句说equals()相等两象hashcode()能相等（我理解由于哈希码候产冲突造）
反：hashcode()等定能推equals()等；hashcode()相等equals()能相等能等
我理解哈

❽ java查看hashmap的源码发现并没有向entrySet中装入元素，而去可以如下遍历。

首先hashmap保存了一个属性
private transient Set<Map.Entry<K,V>> entrySet = null;
下面是hashmap的put方法。
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
在你put元素进去的时候就自动填进去了。在remove等操作也是包含的。
Entry是hashmap的一个内部类。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
}
方法我就不写了。该内部类保存了一个当前的一个key值value值，还包含指向下一个Entry的引用。写的不仔细，没有工具查看，直接看源码文件的不方便。

❾ HashMap源码中put方法里面e.hash == hash && ((k = e.key) == key || key.equals(k))

我认为这个是比较效率的问题，这样写可以尽量少的调用equals
如果把e.hash == hash去掉，只用equals比较，效率太低
(k = e.key) == key如果是true说明是同一个对象，就不用equals了，效率较高

❿ 同步的数据结构，例如concurrenthashmap的源码理解以及内部实现原理，为什么他是同

nized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的不同部分进行的修改。ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分，每个段其实就是一个小的hash table，它们有自己的锁。只要多个修改操作发生在不同的段上，它们就可以并发进行。
有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。这里“按顺序”是很重要的，否则极有可能出现死锁，在ConcurrentHashMap内部，段数组