C/C++教程

hashMap 与hashTable的区别 concurrentHashMap

本文主要是介绍hashMap 与hashTable的区别 concurrentHashMap,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
hashMap 1.7底层:数组+链表  采用头插法 (当多个key发生hash冲突,就会让链表过长,查询效率较低,时间复杂度为O(n))
hashMap 1.8底层 :数组+链表+红黑树  采用尾插法  当数组容量>=64且链表长度>8 就会转换为红黑树 时间复杂度为log(On)
hashMap 允许key设置null
无论是1.7版本还是1.8版本  都会产生线程安全问题
在多线程情况下 同时操作 使用put方法
会共享同一个table数组 发生线程安全问题


hashTable  在put方法 上加了sync锁(锁住的是整个对象或者说是整个table数组),当多个线程访问put方法,是需要进行锁的竞争 锁的粒度较大 只能等到put释放 才能get,继续抢锁 ,get是不会出现线程安全问题,但是期间只能阻塞等待
hashTable 无法将key 设置null
concurrentHashMap 1.7底层
数据结构:数组+Segments分段锁(相当于多个hashTable)+HashEntry链表实现
锁的实现:Lock锁+CAS锁+UNSAFE类

分段锁设计:将大的hashTable 集合拆分成n个小的HashTable 集合  默认分成16个Segments
核心思想:减少多个线程锁的竞争,不会在访问到同一个hashTable
    当多个线程进行put操作 会根据key计算具体存放hashTable的位置(如果计算的hashTable 位置不一致  则不会发生锁的竞争)如果计算hashTable位置一致  则会发生锁的竞争
计算hashTable 公式 key.hashCode()%HashTable.size

concurrentHashMap 1.8 底层
数据结构:Node数组
数组+链表+红黑树
锁的实现: 取消了Segments分段设计
index 没有发生冲突使用CAS锁
index发生冲突使用Sync锁

concurrentHashMap get方法是没有加锁的
手写concurrentHashMap 底层源码
public class ConcurrentHashMapDemo<K,V> {
    /*由16个hashTable组成*/
    private Hashtable[] hashtable;

    public ConcurrentHashMapDemo() {
        hashtable=new Hashtable[16];
        for (int i = 0; i < hashtable.length; i++) {
            //每个hashTable 位置new 小的hashTable
            hashtable[i]=new Hashtable();
        }
    }
    public void put(K k,V v){
        //计算出key值存放的hashTable中的位置
        int hashTableIndex = k.hashCode() % hashtable.length;
        //将key存入计算出索引位置的小hashTable中即可
        hashtable[hashTableIndex].put(k, v);
    }
    public V get(K k){
        int hashTableIndex = k.hashCode() % hashtable.length;
       return (V) hashtable[hashTableIndex].get(k);
    }
    public static void main(String[] args) {
        ConcurrentHashMapDemo<String, String> concurrentHashMap = new ConcurrentHashMapDemo<>();
        concurrentHashMap.put("lcc", "123");
        concurrentHashMap.put("xxoo", "33");
        concurrentHashMap.put("ooxx", "3");
        System.out.println(concurrentHashMap.get("lcc"));
        System.out.println(concurrentHashMap.get("xxoo"));
        System.out.println(concurrentHashMap.get("ooxx"));


    }


}

 

这篇关于hashMap 与hashTable的区别 concurrentHashMap的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!