郏俊龙个人博客

java数据结构总结(hashMap,hashTable)

—

由

youximao
于

[toc]

为什么

总觉得java学习了这么久也要多来一些基础的，也是对原来零散的记忆的一些总结吧

个人认为基础这种东西永远不会过时，学了就是好的。基础思想都是相通的。

参考:http://wiki.jikexueyuan.com/project/java-collection/ 这个是基于1.7的 hashmap还是看jdk8好,改了不少呢

hashMap

  • 构造的时候 含有数量initialCapacity和负载因子默认16 负载0.75,由于 while(capacity<initialCapacity)capacity<<=1;每次扩张一倍； 
    // 这个是采用位运算，最高位为1 然后右移把他的位全部变成1后 加1 即可实现只有一个1；
static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;
    ……
}
有一个next 就是表示当hash相同时使用链表

put

  • 添加：先判断key是否为null，因为hashmap允许key或value为null，但不能同时；为null使用return putForNullKey(value);不为空,通过indexFor(hash,table)判断当前hash值下是否有值,有只就只能遍历链表的next对比key是否相同, 

       // 对hash相同的 进行链表遍历
   for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            // key 相同就修改
            if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
            // 找不到key就插入到链表中，如果大于8就整理树
            if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
        }
      //根据上一步骤中求出的hash得到在数组中是索引i
        int i = indexFor(hash, table.length);
     // 没有key的化 就添加到索引i，
       ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
  • add方法就是这样判断key，为null，存在修改，不存在就添加然后判断是否resize 扩容.“

get

  • 读取就很简单了： 就是通过hash 获取table[]里面的firstEntity,然后遍历链表即可

    final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

resize

当 HashMap 中的元素个数超过数组大小 loadFactor时，就会进行数组扩容，loadFactor的默认值为 0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为 16，那么当 HashMap 中元素个数超过 160.75=12 的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，
– jdk1.8与1.7最大的不同就是不是每个都计算一下hash值然后算索引;而是
我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap
– ** 通过进行判断if ((e.hash & oldCap) == 0)**
– 这样访问一条链表时，就可以将一条链表分成两条链表，然后newTab[j] = loHead;,newTab[j + oldCap] = hiHead;

JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是JDK1.8不会倒置
resize参考: https://tech.meituan.com/java-hashmap.html

  • 遍历方式:
    1. 使用entrySet:效率高,Iterator iter= map.entrySet().iterator()
    2. map.keySet 效率很低
    3. 代码如下
       // 第一个是lambda的访问使用
    map.forEach((key, value) -> {
    });

    for (Map.Entry<String,String>jia:map.entrySet()) {
    }
    for (String value:map.keySet()) {
    }

hashTable

和hashMap也是键值对的构造,1.7与1.8没有变化

  • table是一个 Entry[] 数组类型，而 Entry（在 HashMap 中有讲解过）实际上就是一个单向链表。哈希表的”key-value键值对”都是存储在Entry数组中的。
  • count 是 Hashtable 的大小，它是 Hashtable 保存的键值对的数量。
  • threshold 是 Hashtable 的阈值，用于判断是否需要调整 Hashtable 的容量。threshold 的值=”容量*加载因子”。
  • loadFactor 就是加载因子。
  • modCount 是用来实现 fail-fast 机制的。

  • 构造函数: 就是new Entry[initialCapacity];一个Entry的数组;默认init是11,负载因子为0.75

    if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  • put:先判断value是否为空,key一定 不能为空.
  //也是求hash 然后对entry进行遍历,key相同就修改原值,不同就进行下面的赋值
  Entry tab[] = table;
  int hash = hash(key);    //计算key的hash值
  int index = (hash & 0x7FFFFFFF) % tab.length;     //确认该key的索引位置
  // 在索引位置处插入一个新的节点
  Entry<K,V> e = tab[index];
  // 这个就是插入链表的操作,把next放入下一个
  tab[index] = new Entry<>(hash, key, value, e);
  • rehash()
//还是那种1.7的计算hash重新分配,不是hashMap的那种好用的
        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                Entry<K,V> e = old;
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = (Entry<K,V>)newMap[index];
                newMap[index] = e;
            }
        }

hashMap与hashTable区别

  1. HashTable 基于 Dictionary 类，而 HashMap 是基于 AbstractMap。Dictionary 是任何可将键映射到相应值的类的抽象父类，而 AbstractMap 是基于 Map 接口的实现，它以最大限度地减少实现此接口所需的工作。
  2. HashMap 的 key 和 value 都允许为 null，而 Hashtable 的 key 和 value 都不允许为 null。HashMap 遇到 key 为 null 的时候，调用 putForNullKey 方法进行处理，而对 value 没有处理；Hashtable遇到 null，直接返回 NullPointerException。
  3. Hashtable 方法是同步，而HashMap则不是。我们可以看一下源码，Hashtable 中的几乎所有的 public 的方法都是 synchronized 的，而有些方法也是在内部通过 synchronized 代码块来实现。所以有人一般都建议如果是涉及到多线程同步时采用 HashTable，没有涉及就采用 HashMap，但是在 Collections 类中存在一个静态方法：synchronizedMap()，该方法创建了一个线程安全的 Map 对象，并把它作为一个封装的对象来返回。

HashSet

HashSet 而言，它是基于 HashMap 实现的，底层采用 HashMap 来保存元素public HashSet() {map = new HashMap<>();}

对象要实现equals()和hashCode的方法,然后comparetor方法调用

  • 添加key的时候public boolean add(E e) {return map.put(e, PRESENT)==null;} map.put(e,object)==null;是object是一定相同的,当e相同时map.put会进行判断由于value会相同然后map.put会更新value;
    所以set也是进行插入不管key怎么样,但是插入的值不变,每次传递给map时,map会对hash 和 equla判断,进行的是旧值刷新的功能,因为value是不变的,key重复不怕,我每次都插入变更新,当时候还是一个key;
    感觉效率不高呀

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注