HashMap介绍
HashMap是开发中使用频率最高的用于映射(键值对 key value)处理的数据结构,我们经常把hashMap数据结构叫做散列链表;
ObjectI entry<Key,Value>,entry<Key,Value>] 可以将数据通过键值对形式存起来
特点
HashMap根据键的hashcode值存储数据,大多数情况可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序是不确定的想要使得遍历的顺序就是插入的顺序,可以使用LinkedHashMap,LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。
线程不安全的HashMap
因为多线程环境下,使用Hashmap进行put操作会引起死循环,导致CPU利用率接近100%,所以在并发情况下不能使用HashMap。
HashMap最多只允许一条记录的键为null,允许多条记录的值为nullHashMap非线程安全,如果需要满足线程安全,可以一个Collections的synchronizedMap方法使HashMap具有线程安全能力,或者使用ConcurrentHashMap效率低下的HashTable容器
HashTable容器使用synchronized来保证线程安全,但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时,其他线程访问HashTable的同步方法时,可能会进入阻塞或轮询状态。如线程1使用put进行添加元素,线程2不但不能使用put方法添加元素,并且也不能使用get方法来获取元素,所以竞争越激烈效率越低。
ConcurrentHashMap的锁分段技术
HashTable容器在竞争激烈的并发环境下表现出效率低下的原因,是因为所有访问HashTable的线程都必须竞争同一把锁,那假如容器里有多把锁,每一把锁用于锁容器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效的提高并发访问效率,这就是ConcurrentHashMap所使用的锁分段技术,首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。
通常会见到数据库优化,具体就是索引优化,那什么是索引优化呢?
举个例子,微信通讯录,最右侧会有a-z的排序,这就是索引,把数据分组,用到了hashMap数据结构
为什么键一个set集合,值是一个value集合
HashMap源码分析
核心成员变量
hashMap常量
构造方法
常用方法
什么是HASH
是根据文件的内容的数据 通过逻辑运算得到的数值, 不同的文件(即使是相同的文件名)得到的HASH值是不同的, 所以HASH值就成了每一个文件在EMULE里的身份证.
secondary : 第二的table:存储键值对的数组tab.lenth=下标最大值e:tab[index] : 一维数组第一个元素,整个链表的头结点
put方法
下1 代表下一个代码块有此方法 下下2 代表下下一个代码块有此方法 依次类推
hashMap不仅仅是一种单纯的一维数组,有键key,有值value,还有next指针,这样的好处是HashMap根据键的hashcode值存储数据,大多数情况可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序是不确定的
oldCapacity:扩容之前的长度
newTable:
table[index] = next 也就是链表中下一个元素
table[index]就相当于微信同一个索引下的某个元素,有两个了,再添加,就用next指向下一个元素串只需要用头结点来表示,要做到是先把新结点连接到串里面来,然后再让tab[index]等于这个串,这个串本身就是这个头结点,比如现在有三个串(头结点也有一个),新进来的串放在前面
上图的蓝色部分:蓝色为新结点,放在tab[index]里面来,就是头结点,相当于新结点变成了头结点,而新结点作为头结点的next指针,作为一个引用引进来了
上截图中的第二图:这个图就是,tab[index]这个一维数组中的某个元素或存储区域,让它等于新加进来的元素--newHashMap,让新进来的元素的next指针指向tab[index]
remove
tab[index]:头结点
prev=null 默认为空
要删除一个key1,找到下标索引就是index=0 第一列,但是这个index=0有很多键值对,不能直接把index=0里的所有键值对删除吧,所以要先查找找出来,删除需要的键值对
修改元素:
元素的修改也是put方法,因为key是唯一的,所以修改元素,是把新值覆盖旧值。
第一排,只有最后4位才有效,因为与运算全是1才为1,所以0000=1001=0(最小值)1001+1001=9(最大值)
hash%10也是(0~9),因为hash不固定
与运算lenth-1均匀的分布成0~9 或运算分成两个区间
hash相同 key不一定相同>> key1 key2产生的hash很有可能是相同的,如果key真的相同,就不会存在散列链表了,散列链表是很多不同的键算出的hash值和index相同的
key相同 经过两次hash hash一定相同
tips
想理解数据结构源码,得理清楚当一个新的元素被添加进来以后,会和之前的老的元素产生什么关系首先看继承的关系,看成员变量,看元素之间的关系,看元素之间的关系就是在添加元素的时候,这组元素和之前的元素有什么关系,put方法