首页 > 代码库 > java-HashMap分析

java-HashMap分析

(一)哈希算法

哈希算法,将原始数据通过散列函数映射为较短的固定长度的二进制值,简称哈希值。

hash算法有两个基本特点:可重复和不可逆。理论上计算出的哈希值是可重复的,但好的散列函数基本不会出现这种情况。不可逆指,知道哈希值无法推算出原始数据。

哈希算法一般用于快速查找(如HashMap)和加密算法(如MD5)。


(二)java中的hashcode

java中对象基类Object有hashcode方法,native调用默认返回对象内存地址,hashcode返回不定长的10进制数。

Java对于eqauls方法和hashCode方法是这样规定的:1、如果两个对象相同(equal),那么它们的hashCode值一定要相同;2、如果两个对象的hashCode相同,它们并不一定相同。 

hashcode可以重写,String重写了hashcode。

public int hashCode() {
	int h = hash;
        int len = count;
	if (h == 0 && len > 0) {
	    int off = offset;
	    char val[] = value;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 

使用 int 算法,这里 s[i] 是字符串的第 i 个字符,n 是字符串的长度,^ 表示求幂。(空字符串的哈希码为 0。)


(三)hashmap源码分析

数据格式:数组和链表结合的拉链法哈希表。


    /**
     *整个HashMap的基本数据结构
     */
    transient HashMapEntry<K, V>[] table;
    
    static class HashMapEntry<K, V> implements Entry<K, V> {
        //put(key,value)中的key
        final K key;
        //put(key,value)中的value
        V value;
        //经过哈希映射函数计算出的hash值
        final int hash;
        //指向下一个HashMapEntry
        HashMapEntry<K, V> next;

        HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
            this.key = key;
            this.value = http://www.mamicode.com/value;>
public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        //防止质量较差的哈希函数带来过多的冲突(碰撞)问题,进一步使用映射函数生成值
        int hash = hash(key.hashCode());
        //计算出该hash属于哪个数组位置坐标
        int i = indexFor(hash, table.length);
        //检测该key是否已存在于数组为i的链表中
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //hash相同,key不一定相同
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = http://www.mamicode.com/e.value;>

(四)HashMap和HashTable的区别

1.继承不同

Hashtable extends Dictionary
HashMap  extends AbstractMap
2.同步

HashMap是非同步的,HashTable是同步的

3.插入值

HashMap键值允许为null,HashTable不允许

HashMap通过get方法获取到null不代表不存在该key,必须用containsKey()方法来判断。

HashMap<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("1", null);
        System.out.println(hashMap.get("1"));//null
        System.out.println(hashMap.get("2"));//null




java-HashMap分析