首页 > 代码库 > 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
2.同步HashMap extends AbstractMap
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分析
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。