hashmap算法
① 面试中如何回答HashMap的工作原理
用过哪些Map类，都有什么区别，HashMap是线程安全的吗,并发下使用的Map是什么，他们
内部原理分别是什么，比如存储方式，hashcode，扩容，默认容量等。
java8的ConcurrentHashMap为什么放弃了分段锁，有什么问题吗，如果你来设计，你如何
设计。
有没有有顺序的Map实现类，如果有，他们是怎么保证有序的。
hashmap的实现原理，https://blog.csdn.net/mbshqqb/article/details/79799009
下面是自己的总结:
存储结构:
里面存储的是一个entry数组，每个数组元素中的结构是一个entry链表
Entry是map中的一个静态内部类，其中的变量有:key,value,hashcocd,下一个Entry
什么是hash？
又称散列，将任意长度的输入通过散列算法转换成固定长度的输出，该输出就是散列值。这是一种压缩映射，散列值的空间通常远小于输出的空间。不同的输入有可能会散列出相同的输出，因此不能从散列值来确定唯一的输入值。这也是为什么比较两个对象不能仅仅使用hashcode方法比较的原因。
hash碰撞:
对不同的值进行hash运算生成了相同的散列值。这个是不可避免的，但是我们需要尽量的减少其带来的损失。
(1)设计好的hash算法让其尽可能的分布均匀
hashmap中的hash算法解析
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
让key的hashcode本身与它右移16位异或，是为了让它的高位与低位混合，增加低位的随机性，同时也变相保持了高位的特征
计算元素位置的算法:
int index = hash & (arrays.length-1);
那么这也就明白了为什么HashMap的数组长度是2的整数幂。比如以初始长度为16为例，16-1 = 15，15的二进制数位00000000 00000000 00001111。可以看出一个基数二进制最后一位必然位1，当与一个hash值进行与运算时，最后一位可能是0也可能是1。但偶数与一个hash值进行与运算最后一位必然为0，造成有些位置永远映射不上值。
对于null值的处理
hashmap是接受null值的，null值被放在数组的第一个元素当中，取出来的时候怎么处理呢？
hashmap的工作原理？
它的里面有一个Entry数组，在put时我们先根据key值计算出hashcode，进而计算出该元素在数组中的位置，将健值对封装在Map.Entry对象中，然后存储在数组中
若产生hash冲突怎么办？
每个数组元素的位置都是一个链表结构，若计算出来的hashcode相同则将元素追加到该链表当中，这是hashmap的处理方式
在取元素的时候，先计算key值对应的hashcode ，找到元素所在的位置，然后调用key的equals方法去遍历链表，最后找到元素
还有哪些解决hash冲突的方法？
开放寻址法
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
再哈希法
这种方法是同时构造多个不同的哈希函数：
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
链地址法
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
建立公共溢出区
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
默认的负载因子0.75
当map的大小超过当前容量的百分之75时会进行自动扩容，会将原来的对象重新放到新的数组中
rehash 的过程是什么样子的？
说白了就是先resize，生成一个新的Entry数组，再transfer将原数组中的值重新计算index放入新的数组中，然后改变阈值为新的长度x负载因子
如果key为null，这始终会被散列到table[0]的桶中，即使是rehash的过程也是一样。非null的key也有可能会被散列到table[0]的位置，例如上图中key=“f”，而且相同的key在在不同的时间可能会被散列到不同的位置，这与rehash有关。
这个过程中容易发生什么问题呢？
容易产生条件竞争，如果在扩容的过程中put数据，会造成意想不到的结果。或者如果两个线程都触发了扩容，也会存在问题
这块有没有遇到过什么比较好的例子？
jdk1.8以后改成了红黑树，为什么？说一下红黑树的原理？
hashmap与hashtable的区别？
HashTable和HashMap的实现原理几乎一样，差别无非是
HashTable不允许key和value为null
HashTable是线程安全的
但是HashTable线程安全的策略实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁。
多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。
篇幅有限，未完待续
② JAVA中的HASHSET和HASHMap的底层实现是怎样的大致讲一下。
HASHMAP是根据HASH算法储存数据的集合类，每一个存入其中的对象都有一个特定的哈希值！当我们新建一个HashMap对象，如果不给定它的大小，其默认为16，就相当与下面新建了编号为0到15的数组(链表数组)。以默认HashMap为例，put一个对象时，首先得到他的哈希值，在与十五相除得到余数，找到与余数相同编号的数组插入其中！HASHSET就是没有value值的HASHMAP，你可以新建一个HASHSET,插入0到15，绝对以0到15的顺序打印。
③ 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。
④ 求高手给解答一下 HashMap 的存储结构，说的越清楚越好，谢谢
HashMap存储结构浅析
1.hashmap是按照存储结构来讲是数组(散列桶)与链表的组合体.
2. 如何计算hashmap中的散列桶的位置。
首先hashcode的值是用来辅助计算散列桶的位置的。如何散列有不同的算法，比如%或 & (散列桶的length-1)
hashmap内部实现会把hashcode的值通过移位等运算再加工一下，保证加工之后的值二进制串中的01分布更加均匀. 数组的index或散列桶的位置等于h & (length-1); 由于length初始值是16, 将来也是基于2的倍数进行自动扩展. 所以length - 1的binary形式一定是一堆1，然后做与运算的结果就是取优化后哈希值的低位
index一定会<=length-1. 正好做为数组的下标. 注意，通常根据hashcode计算散列桶的算法是%。
由于数组的长度默认是16,并且会以2的倍数resize，当数组变大之后，会将以前数组中的每个entry的key重新hash到新的数组里：index=h & (newlength-1)
3.与运算会将计算出的哈希值转换成正的吧？上面有提到过溢出的问题，这样可能会导致二进制符号位为1，得出的值是负数
->HashMap的代码实现，里面的MAX_CAPACITY是Integer Max Value的一半，也就是低位的部分不可能出现在符号位上
注:int是32位,通常最左边的位是符号位. 如果数组的容量length最大的值才是Integer Max Value的一半,那么与之后不会肯定影响到符号位的值.
4.字符串如何计算hashcode
for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
如果h的值随着字符串的增长而超过32整型的值.
不管它如何增大，它只取32位(即使超过32位)，所以说会出现负数(超过32位时,32位应该是1. 这样截取之后,首位是1就会表示负数)。
hashcode的范围就是一个int的范围-2^32到2^31
5.
5. 散列的目的是索引化访问
如果一个map使用array来实现，第一个array里面存放key，第二个存放value，k-v的index一致。这样的存储结构，如果要去匹配某个key，需要遍历key array的元素，才能找到。这样查找的效率与array的长度成反比。散列表的出现就是在速度与存储空间找到一个平衡并且每次查找的时间是恒定的, 散列表的目的就象通过index访问array那样，将一切索引化。比如通过hashcode去定位散列桶。散列桶中的元素有可能冲突。hashmap的解决是继续通过equal去比较冲突的元素是否相等。
又例如hashmap的数组位置是0～7。又假如要把某个类的实例存放在以上8个位置中，如果不用hashcode而任意存放，那么当查找时就需要到每个位置去找。
假如类中字段ID,如果hash算法是hashcode＝ID％8，以后在查找该类时就可以通过ID除8 求余数直接找到存放的位置。
但是如果两个类的实例的hashcode被散列到同一个桶，例如9除以8和17除以8的余数都是1，这时9和17就存在冲突，这时就需要equals去进一步比较冲突的元素是否相等。
hashcode来定位实例的散列桶位置然后再通过 equals判断该桶里面的元素是否逻辑相等。
所以二者的用途一定要区分：equals是用来判断是否逻辑相等。hashCode是与hashset,hashtable,hashmap之类的数据结构使用时，用来快速定位散列桶。
6.数据结构get/add与hashcode和equal
6.1 HashSet
对于Set接口的实现类HashSet，它是按照哈希算法来存取集合中的对象，并且因为其继承了Set接口，所以不允许加入相同的元素，这就要使用到equals()和hashCode()方法了。在往HashSet里面添加对象的时候，在Add()的方法内部，它首先调用该对象的hashCode()方法，如果返回的哈希码与集合已存在对象的哈希码不一致（HashMap会缓存放入元素的hashcode值，方便比较，HashSet有可能一样，如果存在一样的hashcode，add失败，直接返回），则add()方法认定该对象没有与集合中的其它对象重复，那么该对象将被添加进集合中。如果hashCode()方法返回的哈希码与集合已存在对象的哈希码一致，那么将调用该对象的equals方法，进一步判断其是否为同一对象（根据java规范，并不强制不相等的二个对象拥有不相等的hashcode，这样就导致不相等的二个对象可能存在一样的hashcode，所以，倒过来，先判断hashcode相等并不能决定二个对象也一定相等，所以，还需要进一步判断equal来决定，以便add即使hashcode相同，但是equal不同的元素到hashset里）.
6.2 HashMap 具体可以参考effective java 39~40
hashmap的contains方法与get类似，在使用contains之前，先检查元素的类里面是否实现了hashcode,equal方法。下面的示例中equal中使用id去判断是否相等，hashcode里面一样，也只能使用id去生成。尽量使hashcode里面的元素与equal里面的元素一致。 具体原因可以参考effective java 39~41. 下面示例中直接使用id是因为从第三方调用返回的数据都有id值，并不是需要保存后才会生成id的场景。后一种就不能使用id去判断了。
@Override
public int hashCode()
{
final int prime = 31;
int result = 1;
result = prime * result + ((m_sId == null) ? 0 : m_sId.hashCode());
return result;
}
@Override
public boolean equals(Object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
SNSProfile other = (SNSProfile) obj;
if (m_sId == null)
{
if (other.m_sId != null)
return false;
}
else if (!m_sId.equals(other.m_sId))
return false;
return true;
}
7.String 类的hashcode的生成函数中
for (int i = 0; i < len; i++) { h = 31*h + val[off++]; }
为什么要用31×h，这个数字是怎么算出来的或者说用31有什么好处
->
这 种方法HashCode的计算方法可能最早出现在Brian W. Kernighan和Dennis M. Ritchie的《The C Programming Language》中，被认为是性价比最高的算法（又被称为times33算法，因为C中乘数常量为33，JAVA中改为31），实际上，包括List在 内的大多数的对象都是用这种方法计算Hash值。
9.hashmap的容量是按照2的次方增长,所以length-1的二进制值都是1.
8.resize中的transfer方法
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j =0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e !=null) {
src[j] =null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
//将newTable[i]的引用（C里面的指针）赋给了e.next。也就是使用了单链表的头插入方式（还有种是在尾插入方式）
e.next = newTable[i];
newTable[i] = e;//将e插入后做为第一个节点。上一步e.next的指向是旧的第一个节点。
e = next;
} while (e !=null);
}
}
}
HashMap与LinkedHashMap的区别：LinkedHashMap中的key是按照插入的顺序排序。不象HashMap的key是无序的。主要用在有序访问map的场景
⑤ java 为什么使用hashmap
首先当我们需要存储数据的时候，动态数组虽然能够自动扩容，但是必须在初始时刻指定初始容量。而对于那些在编译时无法确定具体的数量即动态增长的数据，就需要用到Java集合类了。对于ArrayList 和 LinkedList，还有 Vector它们都有一些缺点，要么插入删除速度慢、要么就是遍历速度慢。那么有没有一种插入、删除、遍历都比较不错的集合类呢？于是 HashMap 就出现了。HashMap 是一个散列表，它存储的是一组键值对(key-value)的集合，并实现快速的查找。
（1）为了实现快速查找，HashMap 选择了数组而不是链表。以利用数组的索引实现 O(1) 复杂度的查找效率。
（2）为了利用索引查找，HashMap 引入 Hash 算法, 将 key 映射成数组下标: key -> Index。
（3）引入 Hash 算法又导致了 Hash 冲突。为了解决 Hash 冲突，HashMap 采用链地址法，在冲突位置转为使用链表存储。
（4）链表存储过多的节点又导致了在链表上节点的查找性能的恶化。为了优化查找性能，HashMap 在链表长度超过 8 之后转而将链表转变成红黑树，以将 O(n) 复杂度的查找效率提升至 O(log n)。
【综上】
HashMap 存在的意义就是实现一种快速的查找并且插入、删除性能都不错的一种 K/V（key/value）数据结构。
附上一位博主的高见：网页链接
⑥ Java hashMap合并算法
用Kotlin语言写了一下，Java只要把MutableMap改成Map就可以了
importkotlin.random.Random;
funmain(arg:Array<String>){
println("HelloWorld");
valmap:Map<String,String>=hashMapOf(
"1242"to"A31_001","2424"to"A31_001",
"3646"to"A31_002");
println("原map:$map");
valgroups:HashMap<String,MutableMap<String,String>>=hashMapOf();
for((k,v)inmap.entries){
if(!groups.containsKey(v))groups.put(v,hashMapOf());
valm=groups.getValue(v);
m.put(k,v);
}
println("重组新map:$groups");
//给换成新随机id,没必要但为满足要求
valnewMap:HashMap<Int,MutableMap<String,String>>=hashMapOf();
varid:Int;
for(vingroups.values){
do{id=Random.nextInt();}
while(newMap.containsKey(id));
newMap.put(id,v);
}
println("新随机生成ID:$newMap");
}
>Task:run
HelloWorld
原map:{1242=A31_001,3646=A31_002,2424=A31_001}
重组新map:{A31_002={3646=A31_002},A31_001={2424=A31_001,1242=A31_001}}
新随机生成ID:{-91779881={2424=A31_001,1242=A31_001},2102779363={3646=A31_002}}
BUILDSUCCESSFULin0s
⑦ hashmap算法复杂度为什么为O(1)
因为hashMap内部维护了一个Entry数组，hashcode即数组下标，根据key.hashcode()即可在数组中get到Entry对象，即O(1)。当然，这是理想情况。
倘若数据量大，则可能发生hash碰撞，即一个hashcode可能对应多个key，这时候这个Entry数组中的元素就不是Entry了，而是一个Entry链表。调用map.get(key)的时候，遇到了链表，则会遍历链表，调用equals方法比较key。当然，jdk8做了优化，链表长度超过8的时候，会转变为红黑树结构。当然，除了数据量之外，发生hash碰撞的概率还跟负载因子loadFactor有关。
⑧ Android开发 HashMap如何排序
HashMap排序是数据结构与算法中常见的一种排序算法。本文即以Android平台为例来实现该算法。
具体代码如下： public static void main(String[] args) { Map<String, Integer> map = new HashMap<String, Integer>(); map.put("lisi", 5); map.put("lisi1", 1); map.put("lisi2", 3); map.put("lisi3", 9); List<Map.Entry<String, Integer>> infoIds = new ArrayList<Map.Entry<String, Integer>>( map.entrySet()); System.out.println("--------------排序前--------------"); for (int i = 0; i < infoIds.size(); i++) { String id = infoIds.get(i).toString(); System.out.println(id); } // 排序 Collections.sort(infoIds, new Comparator<Map.Entry<String, Integer>>() { public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) { return ( o1.getValue()-o2.getValue()); } }); System.out.println("--------------排序后--------------"); for (int i = 0; i < infoIds.size(); i++) { Entry<String,Integer> ent=infoIds.get(i); System.out.println(ent.getKey()+"="+ent.getValue()); }}
⑨ HashMap是什么东西
HashMap，中文名哈希映射，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。HashMap数组每一个元素的初始值都是Null。
HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了异步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
(9)hashmap算法扩展阅读：
因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。
HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可。