⑴ hashmap底层是怎么实现的
当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。addEntry(hash, key, value, i)方法根据计算出的hash值，将key-value对放在数组table的 i 索引处。addEntry 是HashMap 提供的一个包访问权限的方法（就是没有public，protected，private这三个访问权限修饰词修饰，为默认的访问权限，用default表示，但在代码中没有这个default），
⑵ hashmap的数据结构，为什么新添加的节点要添加到链表头部
链表有多种形式，如：单向链表，双向链表，单向循环链表，双向循环链表。将链表结构定义为list_t,则该类型中一定（至少）存在一个指向下一节点的指针list_t *next;除了这个指针，list_t 中可以包含其它类型的数据，包括结构体变量。
⑶ hashtable和hashmap的区别是什么
一、继承父类不同
Hashtable继承自Dictionary类，而HashMap继承自AbstractMap类；但二者都实现了Map接口。
二、线程的安全性
1、HashTable是同步（方法中使用了Synchronize)的；而HashMap是未同步（方法中缺省Synchronize）的。
2、Hashtable线程安全，因为它每个方法中都加入了Synchronize，在多线程并发的环境下，可以直接使用Hashtable，不需自己在加同步；
HashMap线程不安全，因为HashMap底层是一个Entry数组，当发生hashmap冲突的时候，hashmap是采用链表的方式来解决的，在对应的数组位置存放链表的头结点。对链表而言，新加入的节点会从头结点加入。
三、是否有contains方法
1、HashTable有一个contains(Object value)方法，功能和containsValue方法（Object value)功能一样。
2、HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey。
四、可否允许有null值
key、value都是对象，但是不能拥有重复key值，value值可以重复出现。
1、Hashtable中，key和value都不允许出现null值。
2、HashMap允许null值（key和value都可以），因为在HashMap中null可以作为健，而它对应的值可以有多个null。
五、遍历方式内部实现不同
1.HashTable使用Enumeration，HashMap使用Iterator。
⑷ HashMap为什么不安全
我们都知道HashMap是线程不安全的，在多线程环境中不建议使用，但是其线程不安全主要体现在什么地方呢，本文将对该问题进行解密。
1.jdk1.7中的HashMap
在jdk1.8中对HashMap做了很多优化，这里先分析在jdk1.7中的问题，相信大家都知道在jdk1.7多线程环境下HashMap容易出现死循环，这里我们先用代码来模拟出现死循环的情况：
publicclassHashMapTest{publicstaticvoidmain(String[]args){HashMapThreadthread0=newHashMapThread();HashMapThreadthread1=newHashMapThread();HashMapThreadthread2=newHashMapThread();HashMapThreadthread3=newHashMapThread();HashMapThreadthread4=newHashMapThread();thread0.start();thread1.start();thread2.start();thread3.start();thread4.start();}}{privatestaticAtomicIntegerai=newAtomicInteger();privatestaticMapmap=newHashMap<>();@Overridepublicvoidrun(){while(ai.get()<1000000){map.put(ai.get(),ai.get());ai.incrementAndGet();}}}
上述代码比较简单，就是开多个线程不断进行put操作，并且HashMap与AtomicInteger都是全局共享的。
在多运行几次该代码后，出现如下死循环情形：
2.jdk1.8中HashMap
在jdk1.8中对HashMap进行了优化，在发生hash碰撞，不再采用头插法方式，而是直接插入链表尾部，因此不会出现环形链表的情况，但是在多线程的情况下仍然不安全，这里我们看jdk1.8中HashMap的put操作源码：
finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node[]tab;Nodep;intn,i;if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;if((p=tab[i=(n-1)&hash])==null)//如果没有hash碰撞则直接插入元素tab[i]=newNode(hash,key,value,null);else{Nodee;Kk;if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;elseif(pinstanceofTreeNode)e=((TreeNode)p).putTreeVal(this,tab,hash,key,value);else{for(intbinCount=0;;++binCount){if((e=p.next)==null){p.next=newNode(hash,key,value,null);if(binCount>=TREEIFY_THRESHOLD-1)//-1for1sttreeifyBin(tab,hash);break;}if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;p=e;}}if(e!=null){//=e.value;if(!onlyIfAbsent||oldValue==null)e.value=value;afterNodeAccess(e);returnoldValue;}}++modCount;if(++size>threshold)resize();afterNodeInsertion(evict);returnnull;}
这是jdk1.8中HashMap中put操作的主函数， 注意第6行代码，如果没有hash碰撞则会直接插入元素。
如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，所以这线程A、B都会进入第6行代码中。
假设一种情况，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，问题出现：线程A会把线程B插入的数据给覆盖，发生线程不安全。
总结
首先HashMap是线程不安全的，其主要体现：
在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。
⑸ HashMap是什么东西
HashMap，中文名哈希映射，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。HashMap数组每一个元素的初始值都是Null。
HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
(5)hashmap头文件扩展阅读：
因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。
HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可。
⑹ 怎样将 hash_map 写入文件，并从文件中读出来
楼主你是什么系统？linux还是windows？在源代码的前面写入一下代码：// just for "#include <hash_*>" in linux#if __GNUC__>2#include <ext/hash_set>#include <ext/hash_map>using namespace __gnu_cxx;#else#include <hash_set>#include <hash_map>using namespace stdext;#endif因为hash_map以前不属于标准库，而是后来引入的。所以在windows下需要使用stlport，然后在setting中加入Additional library path。在linux下使用gcc的时候，引入<hash_map>，使用的时候也说找不到hash_map，而这种后来引入标准库的有两种可能：一种是它被放在了stdext名空间里，那么就要使用using namespace stdext引入该名空间并#include <hash_map>;另一种可能就是它被放在标准库的ext目录底下，这时就仍旧需要使用属于std名空间，这时你的源文件应当#include <ext/hash_map>;如果不知道是哪一种，就需要自己查一下，切换到c++库目录下：cd /usr/include/c++/4.*.* 然后使用grep命令：grep -iR "hash_map" ./ 查看hash_map在哪个头文件中。 找到后进去看一下就知道它到底被包含在哪个命名空间中了。
⑺ hash_map及hash_set用法
#include<hash_map>#include<hash_set>#include<string>#include<iostream>using namespace std;using namespace stdext;int main(){ //建立一个hash_map hash_map<string,int>m; //加入元素 m["A"]=1; m["B"]=2; m["C"]=3; //或者这样加入 m.insert(hash_map<string,int>::value_type("D",4)); m.insert(hash_map<string,int>::value_type("E",5)); //查找 cout<<"查找A"<<endl; hash_map<string,int>::iterator it; //迭代器 it=m.find("A"); //查找键名为A的项 if(it!=m.end()) //若找到，则it不指向最后一个项的下一个 { cout<<"Found!\t"<<(*it).first<<"–>"<<(*it).second<<endl; } //删除键名为A的项 m.erase("A"); //输出各元素 cout<<"删除A之后"<<endl; for(it=m.begin();it!=m.end();++it) cout<<(*it).first<<"–>"<<(*it).second<<endl;//建立一个hash_set hash_set<int>s; //加入元素 s.insert(1); s.insert(2); s.insert(3); //查找元素 hash_set<int>::iterator it2; //查找1 it2=s.find(1); if(it2!=s.end()) { cout<<"Found!"<<endl; } //删除元素 cout<<"删除1"<<endl; s.erase(1); //输出各元素 cout<<"删除1之后的元素"<<endl; for(it2=s.begin();it2!=s.end();++it2) cout<<(*it2)<<endl; return 0;}
⑻ 我的VC6.0没有hash_map头文件咋办
你可以用map，或者自己写一个算法实现hash_map。 你提交的时候不要使用g++，用c++就行了。没有哈希，你用map就行了。用法，你网络一下。
⑼ HashMap为什么哪里不安全
有两个原因
存放数据时,HashMap不是线程安全的
比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。
HashMap在容量不足的时候会进行resize,将自己扩容为原来的两倍,而reszie不是线程安全的
假设有两个线程同时需要执行resize操作，我们原来的桶数量为2，记录数为3，需要resize桶到4，原来的记录分别为：[3,A],[7,B],[5,C]，在原来的map里面，我们发现这三个entry都落到了第二个桶里面。 假设线程thread1执行到了transfer方法的Entry next = e.next这一句，然后时间片用完了，此时的e = [3,A], next = [7,B]。线程thread2被调度执行并且顺利完成了resize操作，需要注意的是，此时的[7,B]的next为[3,A]。此时线程thread1重新被调度运行，此时的thread1持有的引用是已经被thread2 resize之后的结果。线程thread1首先将[3,A]迁移到新的数组上，然后再处理[7,B]，而[7,B]被链接到了[3,A]的后面，处理完[7,B]之后，就需要处理[7,B]的next了啊，而通过thread2的resize之后，[7,B]的next变为了[3,A]，此时，[3,A]和[7,B]形成了环形链表，在get的时候，如果get的key的桶索引和[3,A]和[7,B]一样，那么就会陷入死循环。
⑽ 求高手给解答一下 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.字符串如何计算hashcodefor (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和equal6.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~40hashmap的contains方法与get类似，在使用contains之前，先检查元素的类里面是否实现了hashcode,equal方法。下面的示例中equal中使用id去判断是否相等，hashcode里面一样，也只能使用id去生成。尽量使hashcode里面的元素与equal里面的元素一致。 具体原因可以参考effective java 39~41. 下面示例中直接使用id是因为从第三方调用返回的数据都有id值，并不是需要保存后才会生成id的场景。后一种就不能使用id去判断了。@Overridepublic int hashCode(){ final int prime = 31; int result = 1; result = prime * result + ((m_sId == null) ? 0 : m_sId.hashCode()); return result;} @Overridepublic 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的场景
