HashBiMap

BiMap

HashBiMap

    private V put(@Nullable K key, @Nullable V value, boolean force) {
        int keyHash = smearedHash(key);
        int valueHash = smearedHash(value);
        //  key和value完全相同，直接返回
        BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash);
        if (oldEntryForKey != null
            && valueHash == oldEntryForKey.valueHash
            && Objects.equal(value, oldEntryForKey.value)) {
            return value;
        }
        //  放入值，如果有相同值，force为true时删除旧的从而准备放入新的，否则抛异常
        BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash);
        if (oldEntryForValue != null) {
            if (force) {
                delete(oldEntryForValue);
            } else {
                throw new IllegalArgumentException("value already present: " + value);
            }
        }
        //  将keey,vakue封装为新的Entry
        BiEntry<K, V> newEntry = new BiEntry<>(key, keyHash, value, valueHash);
        //  若key已存在，删除旧的并插入新的
        //  否则只插入新的
        if (oldEntryForKey != null) {
            delete(oldEntryForKey);
            insert(newEntry, oldEntryForKey);
            oldEntryForKey.prevInKeyInsertionOrder = null;
            oldEntryForKey.nextInKeyInsertionOrder = null;
            return oldEntryForKey.value;
        } else {
            insert(newEntry, null);
            rehashIfNecessary();
            return null;
        }
    }
    //  hashTableKToV:key映射到value的桶，遍历找到entry的尽头
    private BiEntry<K, V> seekByKey(@Nullable Object key, int keyHash) {
        for (BiEntry<K, V> entry = hashTableKToV[keyHash & mask];
            entry != null;
            entry = entry.nextInKToVBucket) {
            //  遇到了相同的key
            if (keyHash == entry.keyHash && Objects.equal(key, entry.key)) {
                return entry;
            }
        }
        return null;
    }
    //  hashTableKToV:value映射到key的桶
    private BiEntry<K, V> seekByValue(@Nullable Object value, int valueHash) {
        for (BiEntry<K, V> entry = hashTableVToK[valueHash & mask];
            entry != null;
            entry = entry.nextInVToKBucket) {
            if (valueHash == entry.valueHash && Objects.equal(value, entry.value)) {
            return entry;
            }
        }
        return null;
    }
    //  删除entry方法
    private void delete(HashBiMap.BiEntry<K, V> entry) {
        //  entry在hash桶的位置
        int keyBucket = entry.keyHash & mask;
        HashBiMap.BiEntry<K, V> prevBucketEntry = null;
        //  bucketEntry拿到hash桶的根节点，为链表的根节点，不停向后遍历，直到找到要删除的entry
        for (HashBiMap.BiEntry<K, V> bucketEntry = hashTableKToV[keyBucket];
             true;
             bucketEntry = bucketEntry.nextInKToVBucket) {
            if (bucketEntry == entry) {
                //  prevBucketEntry为null，说明当前节点为链表的头节点，将自己的下一个节点挂到hash桶上即可
                if (prevBucketEntry == null) {
                    hashTableKToV[keyBucket] = entry.nextInKToVBucket;
                } else {
                    //  将链表的前一个entry指向后一个entry,即将entry从链表中删除
                    prevBucketEntry.nextInKToVBucket = entry.nextInKToVBucket;
                }
                break;
            }
            //  未找到，准备下一次遍历，prevBucketEntry为下一次遍历entry的前节点
            prevBucketEntry = bucketEntry;
        }
        //  和删除key大致相同，只是hashTableKToV换成了hashTableVToK
        int valueBucket = entry.valueHash & mask;
        prevBucketEntry = null;
        for (HashBiMap.BiEntry<K, V> bucketEntry = hashTableVToK[valueBucket];
             true;
             bucketEntry = bucketEntry.nextInVToKBucket) {
            if (bucketEntry == entry) {
                if (prevBucketEntry == null) {
                    hashTableVToK[valueBucket] = entry.nextInVToKBucket;
                } else {
                    prevBucketEntry.nextInVToKBucket = entry.nextInVToKBucket;
                }
                break;
            }
            prevBucketEntry = bucketEntry;
        }
        //  在大链表上删除entry
        if (entry.prevInKeyInsertionOrder == null) {
            firstInKeyInsertionOrder = entry.nextInKeyInsertionOrder;
        } else {
            entry.prevInKeyInsertionOrder.nextInKeyInsertionOrder = entry.nextInKeyInsertionOrder;
        }

        if (entry.nextInKeyInsertionOrder == null) {
            lastInKeyInsertionOrder = entry.prevInKeyInsertionOrder;
        } else {
            entry.nextInKeyInsertionOrder.prevInKeyInsertionOrder = entry.prevInKeyInsertionOrder;
        }

        size--;
        modCount++;
    }
    //  添加entry，oldEntryForKey？
    private void insert(HashBiMap.BiEntry<K, V> entry, @Nullable HashBiMap.BiEntry<K, V> oldEntryForKey) {
        int keyBucket = entry.keyHash & mask;
        //  将entry放在hash桶对应位置所保存链表的头部
        entry.nextInKToVBucket = hashTableKToV[keyBucket];
        hashTableKToV[keyBucket] = entry;

        int valueBucket = entry.valueHash & mask;
        entry.nextInVToKBucket = hashTableVToK[valueBucket];
        hashTableVToK[valueBucket] = entry;

        if (oldEntryForKey == null) {
            //  当前entry为新添加的entry，将其放在大链表的尾部
            entry.prevInKeyInsertionOrder = lastInKeyInsertionOrder;
            entry.nextInKeyInsertionOrder = null;
            //  如果当前元素为第一个元素，那么大链表头节点持有引用，
            //  否则前一个结点指向该节点
            if (lastInKeyInsertionOrder == null) {
                firstInKeyInsertionOrder = entry;
            } else {
                lastInKeyInsertionOrder.nextInKeyInsertionOrder = entry;
            }
            lastInKeyInsertionOrder = entry;
        } else {
            //  当前节点替换旧节点（修改原节点的值
            entry.prevInKeyInsertionOrder = oldEntryForKey.prevInKeyInsertionOrder;
            //  若老节点为大链表的第一个节点则大链表头节点指向当前节点
            //  否则前节点改为指向当前节点
            if (entry.prevInKeyInsertionOrder == null) {
                firstInKeyInsertionOrder = entry;
            } else {
                entry.prevInKeyInsertionOrder.nextInKeyInsertionOrder = entry;
            }
            //  将下一个节点由oldEntryForKey重指向到entry
            entry.nextInKeyInsertionOrder = oldEntryForKey.nextInKeyInsertionOrder;
            if (entry.nextInKeyInsertionOrder == null) {
                lastInKeyInsertionOrder = entry;
            } else {
                entry.nextInKeyInsertionOrder.prevInKeyInsertionOrder = entry;
            }
        }

        size++;
        modCount++;
    }

    private void rehashIfNecessary() {
        HashBiMap.BiEntry<K, V>[] oldKToV = hashTableKToV;
        if (Hashing.needsResizing(size, oldKToV.length, LOAD_FACTOR)) {
            int newTableSize = oldKToV.length * 2;

            this.hashTableKToV = createTable(newTableSize);
            this.hashTableVToK = createTable(newTableSize);
            this.mask = newTableSize - 1;
            this.size = 0;

            for (HashBiMap.BiEntry<K, V> entry = firstInKeyInsertionOrder;
                 entry != null;
                 entry = entry.nextInKeyInsertionOrder) {
                insert(entry, entry);
            }
            this.modCount++;
        }
    }