博客专区 > Mr_Qi 的博客 > 博客详情
可"重复"key的HashMap
Mr_Qi 发表于1天前
可"重复"key的HashMap
  • 发表于 1天前
  • 阅读 236
  • 收藏 8
  • 点赞 0
  • 评论 2

腾讯云实验室 1小时搭建人工智能应用,让技术更容易入门 免费体验 >>>   

碰到一些需求需要放入可重复key的HashMap,比如Excel需要报错的行号。

那么如果对象实现过hashCode方法和equals 那么放入到hashMap中会出现可能互相覆盖的情形。

原来你是这样的HashMap 正如这篇文章中的测试所说,互相覆盖。

那么就是IdentityHashMap出场的时候啦~

首先了解一下Object的hashCode方法

/**
 * Returns a hash code value for the object. This method is
 * supported for the benefit of hash tables such as those provided by
 * {@link java.util.HashMap}.
 * <p>
 * The general contract of {@code hashCode} is:
 * <ul>
 * <li>Whenever it is invoked on the same object more than once during
 *     an execution of a Java application, the {@code hashCode} method
 *     must consistently return the same integer, provided no information
 *     used in {@code equals} comparisons on the object is modified.
 *     This integer need not remain consistent from one execution of an
 *     application to another execution of the same application.
 * <li>If two objects are equal according to the {@code equals(Object)}
 *     method, then calling the {@code hashCode} method on each of
 *     the two objects must produce the same integer result.
 * <li>It is <em>not</em> required that if two objects are unequal
 *     according to the {@link java.lang.Object#equals(java.lang.Object)}
 *     method, then calling the {@code hashCode} method on each of the
 *     two objects must produce distinct integer results.  However, the
 *     programmer should be aware that producing distinct integer results
 *     for unequal objects may improve the performance of hash tables.
 * </ul>
 * <p>
 * As much as is reasonably practical, the hashCode method defined by
 * class {@code Object} does return distinct integers for distinct
 * objects. (This is typically implemented by converting the internal
 * address of the object into an integer, but this implementation
 * technique is not required by the
 * Java<font size="-2"><sup>TM</sup></font> programming language.)
 *
 * @return  a hash code value for this object.
 * @see     java.lang.Object#equals(java.lang.Object)
 * @see     java.lang.System#identityHashCode
 */
public native int hashCode();

文章中提到了java.lang.System#identityHashCode 那么我们看一下这两个数据有没有差别

这里面包含了IntegerCache的相关知识可以各位详细看看Integer的源码

我们可以看出hashCode计算出来(未复写Object)的值和identityHashCode计算出来的相同(估计就是一个值?

/**
 * Returns the same hash code for the given object as
 * would be returned by the default method hashCode(),
 * whether or not the given object's class overrides
 * hashCode().
 * The hash code for the null reference is zero.
 *
 * @param x object for which the hashCode is to be calculated
 * @return  the hashCode
 * @since   JDK1.1
 */
public static native int identityHashCode(Object x);

bingo~就是和hashCode返回一样【而toString中并不是内存地址而是hashCode的hexString】

/**
 * Returns a string representation of the object. In general, the
 * {@code toString} method returns a string that
 * "textually represents" this object. The result should
 * be a concise but informative representation that is easy for a
 * person to read.
 * It is recommended that all subclasses override this method.
 * <p>
 * The {@code toString} method for class {@code Object}
 * returns a string consisting of the name of the class of which the
 * object is an instance, the at-sign character `{@code @}', and
 * the unsigned hexadecimal representation of the hash code of the
 * object. In other words, this method returns a string equal to the
 * value of:
 * <blockquote>
 * <pre>
 * getClass().getName() + '@' + Integer.toHexString(hashCode())
 * </pre></blockquote>
 *
 * @return  a string representation of the object.
 */
public String toString() {
    return getClass().getName() + "@" + Integer.toHexString(hashCode());
}

那么来看一下IdentityHashMap对应的实现

/**
 * Constructs a new, empty identity hash map with a default expected
 * maximum size (21).
 */
public IdentityHashMap() {
    init(DEFAULT_CAPACITY);
}
 
/**
 * Constructs a new, empty map with the specified expected maximum size.
 * Putting more than the expected number of key-value mappings into
 * the map may cause the internal data structure to grow, which may be
 * somewhat time-consuming.
 *
 * @param expectedMaxSize the expected maximum size of the map
 * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
 */
public IdentityHashMap(int expectedMaxSize) {
    if (expectedMaxSize < 0)
        throw new IllegalArgumentException("expectedMaxSize is negative: "
                                           + expectedMaxSize);
    init(capacity(expectedMaxSize));
}
 
/**
 * Returns the appropriate capacity for the specified expected maximum
 * size.  Returns the smallest power of two between MINIMUM_CAPACITY
 * and MAXIMUM_CAPACITY, inclusive, that is greater than
 * (3 * expectedMaxSize)/2, if such a number exists.  Otherwise
 * returns MAXIMUM_CAPACITY.  If (3 * expectedMaxSize)/2 is negative, it
 * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
 */
private int capacity(int expectedMaxSize) {
    // Compute min capacity for expectedMaxSize given a load factor of 2/3
    int minCapacity = (3 * expectedMaxSize)/2;
 
    // Compute the appropriate capacity
    int result;
    if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
        result = MAXIMUM_CAPACITY;
    } else {
        result = MINIMUM_CAPACITY;
        while (result < minCapacity)
            result <<= 1;
    }
    return result;
}
 
/**
 * Initializes object to be an empty map with the specified initial
 * capacity, which is assumed to be a power of two between
 * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
 */
private void init(int initCapacity) {
    // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
    // assert initCapacity >= MINIMUM_CAPACITY;
    // assert initCapacity <= MAXIMUM_CAPACITY;
 
    threshold = (initCapacity * 2)/3;
    table = new Object[2 * initCapacity];
}

在传入容量的时候和HashMap不一样 其优先计算了1.5倍 恩 这样不需要开发者考虑expectedSize了

查看其get方法

private static int nextKeyIndex(int i, int len) {
    return (i + 2 < len ? i + 2 : 0);
}
 
/**
 * Returns the value to which the specified key is mapped,
 * or {@code null} if this map contains no mapping for the key.
 *
 * <p>More formally, if this map contains a mapping from a key
 * {@code k} to a value {@code v} such that {@code (key == k)},
 * then this method returns {@code v}; otherwise it returns
 * {@code null}.  (There can be at most one such mapping.)
 *
 * <p>A return value of {@code null} does not <i>necessarily</i>
 * indicate that the map contains no mapping for the key; it's also
 * possible that the map explicitly maps the key to {@code null}.
 * The {@link #containsKey containsKey} operation may be used to
 * distinguish these two cases.
 *
 * @see #put(Object, Object)
 */
public V get(Object key) {
    Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    int i = hash(k, len);
    while (true) {
        Object item = tab[i];
        if (item == k)
            return (V) tab[i + 1];
        if (item == null)
            return null;
        i = nextKeyIndex(i, len);
    }
}

很明显其使用了item==k 其实就是地址的比较

nextKeyIndex这个方法很有意思 看来是用来解决Hash冲突的。hashMap通过链表完成了冲突的解决。{

查看hash方法

/**
 * Returns index for Object x.
 */
private static int hash(Object x, int length) {
    int h = System.identityHashCode(x);
    // Multiply by -127, and left-shift to use least bit as part of hash
    return ((h << 1) - (h << 8)) & (length - 1);
}

直接调用了System.identityHashCode 并且和tab的length进行了hash【和hashMap类似】

那么IdentityHashMap通过挪后2个位置【下一个位置用来放value】来占位置【某些情境下性能确实很差,但是通过threshold为2/3稍微稀疏了一些】

继续查看put方法

/**
 * Associates the specified value with the specified key in this identity
 * hash map.  If the map previously contained a mapping for the key, the
 * old value is replaced.
 *
 * @param key the key with which the specified value is to be associated
 * @param value the value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 * @see     Object#equals(Object)
 * @see     #get(Object)
 * @see     #containsKey(Object)
 */
public V put(K key, V value) {
    Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    int i = hash(k, len);
 
    Object item;
    while ( (item = tab[i]) != null) {
        if (item == k) {
            V oldValue = (V) tab[i + 1];
            tab[i + 1] = value;
            return oldValue;
        }
        i = nextKeyIndex(i, len);
    }
 
    modCount++;
    tab[i] = k;
    tab[i + 1] = value;
    if (++size >= threshold)
        resize(len); // len == 2 * current capacity.
    return null;
}

确实可以看到当hash之后发生碰撞直接找到null可以放入为止。

可以看到查找和插入都比较简单。那么如果移除呢

 此时需要注意了。因为当前移除的hash可能是后面如果和当前hash一样的需要前移

/**
 * Removes the mapping for this key from this map if present.
 *
 * @param key key whose mapping is to be removed from the map
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V remove(Object key) {
    Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    int i = hash(k, len);
 
    while (true) {
        Object item = tab[i];
        if (item == k) {
            modCount++;
            size--;
            V oldValue = (V) tab[i + 1];
            tab[i + 1] = null;
            tab[i] = null;
            closeDeletion(i);
            return oldValue;
        }
        if (item == null)
            return null;
        i = nextKeyIndex(i, len);
    }
 
}

换言之需要当前的数据之后【循环table到头了需要从0从开始】全部数据需要朝前提两个格子知道查找到为null为止

/**
 * Rehash all possibly-colliding entries following a
 * deletion. This preserves the linear-probe
 * collision properties required by get, put, etc.
 *
 * @param d the index of a newly empty deleted slot
 */
private void closeDeletion(int d) {
    // Adapted from Knuth Section 6.4 Algorithm R
    Object[] tab = table;
    int len = tab.length;
 
    // Look for items to swap into newly vacated slot
    // starting at index immediately following deletion,
    // and continuing until a null slot is seen, indicating
    // the end of a run of possibly-colliding keys.
    Object item;
    for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
         i = nextKeyIndex(i, len) ) {
        // The following test triggers if the item at slot i (which
        // hashes to be at slot r) should take the spot vacated by d.
        // If so, we swap it in, and then continue with d now at the
        // newly vacated i.  This process will terminate when we hit
        // the null slot at the end of this run.
        // The test is messy because we are using a circular table.
        int r = hash(item, len);
        if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
            tab[d] = item;
            tab[d + 1] = tab[i + 1];
            tab[i] = null;
            tab[i + 1] = null;
            d = i;
        }
    }
}

其实key也不重复只是判断“equals”的逻辑发生了变化~

共有 人打赏支持
粉丝 103
博文 135
码字总数 117114
评论 (2)
爱吃大肉包
记得用的是==判断key
Mr_Qi

引用来自“爱吃大肉包”的评论

记得用的是==判断key

回复@爱吃大肉包 : 上面查找的时候可以看到用的是==
×
Mr_Qi
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: