昨天实现MVC那个小程序里,建模javaBean的时候用了HashMap.晚上回去的时候看了一下,一点都不难,印象是有点象sql里面的table.想到这里,突然觉得自己的横向思维比逻辑思维要强一点,这样也许不好.
table 是一种容器型数据结构,一个很好的类比就是字典里面的单词和对其详细的解释.表是序偶序列,序偶的第一部分为key,索引,相当于数组里的下标.第二部分是对应的value.table 也称做关联数组, 可以用两个并列的数组来实现,一个保存key,一个保存value.其中java.util 的Map 接口定义了4个实现(not JDK5.0),AbstractMap, HashMap, TreeMap , WeakHashMap.
Map map=new HashMap();
map.put("a", "day");
map.put("b", "month");
map.put("c", "year");
map.put("d", "min");
map.put("e", "second");
map.put("f", "hour");
System.out.println("map=\t"+map); //toString() method.
System.out.println("map.size=\t"+map.size());
System.out.println("map.keySet=\t"+map.keySet());
System.out.println("map.values=\t"+map.values());
System.out.println("map.get(\"c\")=\t"+map.get("c"));
System.out.println("map.remore(\"c\")=\t"+map.remove("c"));
System.out.println("map=\t"+map);
System.out.println("map.size=\t"+map.size());
run result:
map={d=min, a=day, c=year, f=hour, b=month, e=second}
map.size=6map.keySet=[d, a, c, f, b, e]
map.values=[min, day, year, hour, month, second]
map.get("c")=year
map.remore("c")=year
map={d=min, a=day, f=hour, b=month, e=second}
map.size=5
HashMap里的key/value 存储顺序取决于table 的容量和这些对象的hashcode
public static void main(String[] args)
{
printHashCode("abc");
printHashCode("def");
printHashCode("ghi");
printHashCode("jkl");
printHashCode("abc");
}
public static void printHashCode(String word)
{
System.out.println(word+":"+word.hashCode());
}
Run result:
abc:96354
def:99333
ghi:102312
jkl:105291
abc:96354
Hash table是一种类型, 它使用一个特别的函数从key 计算出数据值来确定存储位置,这个特别的函数称为Hash函数.
private static final int MASK=0x7FFFFFFF; //2^32-1
private static final int CAPACITY=11; //capacity is 11
public HashCode()
{
}
public static void main(String[] args)
{
printHashCode("Ohr");
printHashCode("Tor");
printHashCode("Hut");
printHashCode("Rad");
printHashCode("Tag");
printHashCode("Uhr");
}
public static void printHashCode(String word)
{
System.out.println(word+":"+ hash(word));
}
public static int hash(String object)
{
return (object.hashCode()&MASK)%CAPACITY;
}
Run result:
Ohr:73
Tor:45
Hut:13
Rad:99
Tag:4
Uhr:82
这里, (object.hashCode()&MASK)%CAPACITY;
private static final int MASK=0x7FFFFFFF; //2^32-1
private static final int CAPACITY=11; //capacity is 11
capacity is 11, mask=2^32-1=2 147 483 647
object.hashCode()&MASK 是将符号去掉,否则,除余后也是负数.这个程序里,return 的结果必在0~10之间.
Rad:3
Tag:3 出现冲突,最常用的方法就是:
把Tag放在最后(程序举例问题,把上面程序里的abc也改成这里的).这种冲突消除算法的名字是:线性探测算法
如果把capacity 改为101,则return 的结果为0~100, 和我们建立HashMap 对象后的顺序相同(改一前面的程序),我测试了一下,看到结果不同,但起码说明了这个原理(可能是JDK版本不同的原因?)
如果用容量为10的hash table存储6个元素,性能可以的,但是我们如果用6个存取6个呢?
衡量Hash table 的拥挤程度,负载系数(load factor):
实际元素/CAPACITY
如果实际等于容量,则系数是100%,如果系数大于容量,则?
容量的缺省值是100,默认的负载系数为75%.如果超过负载系数,则增大它的容量.
HashMap(int initialCapacity, float loadFactor)
Constructs an empty HashMap with the specified initial capacity and load factor.
线性探测的原理是当一个元素被hash 函数定位到一个已经使用的位置的时候,算法将递增位置索引直到找到一个空位置,如果到了hash表的最后,就跳到初始位置.
平方探测
public static int hash(String object)
{
++size;
int h= (object.hashCode()&MASK)%CAPACITY;
int jump=1;
while(used[h])
{
int g=h;
System.out.print(h+",");
h=(g+jump*jump)%CAPACITY;
jump++;
}
在探测的时候会跳过很多元素,重而位置比较均匀.性能比较高
独立链:
避免冲突,允许Hash每个空位可以放置多个元素,这一方法使用链表来存放多个元素,表的空位被称做吊桶.
Java.util.HashMap 类就是使用的对立链.
