java集合类总结
Posted onjava集合类总结
Saving Data...
正在保存数据...
正在儲存資料...
It so life
love as life
Java集合框架之小结
Posted onJava集合框架之小结
1、Java容器类库的简化图，下面是集合类库更加完备的图。包括抽象类和遗留构件（不包括Queue的实现）：
2、ArrayList初始化时不可指定容量，如果以new ArrayList()方式创建时，初始容量为10个；如果以new ArrayList(Collection c)初始化时，容量为c.size()/*1.1，即增加10%的容量；当向ArrayList中添加一个元素时，先进行容器的容量调整，如果容量不够时，则增加至原来的1.5倍加1，再然后把元素加入到容器中，即以原始容量的0.5倍比率增加。
3、Vector：初始化时容量可以设定，如果以new Vector()方式创建时，则初始容量为10，超过容量时以2倍容量增加。如果以new Vector(Collection c)方式创建时，初始容量为c.size()/*1.1，超过时以2倍容量增加。如果以new Vector(int initialCapacity, int capacityIncrement)，则以capacityIncrement容量增加。
4、集合特点：
- List：保证以某种特定插入顺序来维护元素顺序，即保持插入的顺序，另外元素可以重复。
- ArrayList：是用数组实现的，读取速度快，插入与删除速度慢（因为插入与删除时要移动后面的元素），适合于随机访问。
- Vector：功能与ArrayList几乎相同，也是以数组实现，添加，删除，读取，设置都是基于线程同步的。
- LinkedList：双向链表来实现，删除与插入速度快，读取速度较慢，因为它读取时是从头向尾（如果节点在链的前半部分），或尾向头（如果节点在链的后半部分）查找元素。因此适合于元素的插入与删除操作。
- Set：维持它自己的内部排序，随机访问不具有意义。另外元素不可重复。
- HashSet：是最常用的，查询速度最快，因为 内部以HashMap来实现，所以插入元素不能保持插入次序。
- LinkedHashSet：继承了HashSet，保持元素的插入次序，因为内部使用LinkedHashMap实现，所以能保持元素插入次序。
- TreeSet：基于TreeMap，生成一个总是处于排序状态的set，它实现了SortedSet接口，内部以 TreeMap来实现
- TreeMap：键以某种排序规则排序，内部以red-black（红-黑）树数据结构实现，实现了SortedMap接口，具体可参《RED-BLACK(红黑)树的实现TreeMap源码阅读 》
- HashMap: 以哈希表数据结构实现，查找对象时通过哈希函数计算其位置，它是为快速查询而设计的，其内部定义了一个hash表数组（Entry[] table），元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引，如果有冲突，则使用散列链表的形式将所有相同哈希地址的元素串起来，可能通过查看HashMap.Entry的源码它是一个单链表结构。
- Hashtable:也是以哈希表数据结构实现的，解决冲突时与HashMap也一样也是采用了散列链表的形式，不过性能比HashMap要低。
- LinkedHashMap:继承HashMap，内部实体LinkedHashMap.Entry继承自HashMap.Entry，LinkedHashMap.Entry在HashMap.Entry的基础上新增了两个实体引用（Entry before, after），这样实体可以相互串链起来形成链，并且在LinkedHashMap中就定义了一个头节点（Entry header）用来指向循环双向链的第一个元素（通过after指向）与最后一个元素（通过before指向）。在添加一个元素时，先会通过父类HashMap将元素加入到hash表数组里，然后再会在链尾（header.before指向位置）添加（当然这一过程只是调整LinkedHashMap.Entry对象内部的before, after而已，而不是真真创建一个什么新的链表结构向里加那样）；删除先从hash表数组中删除，再将被删除的元素彻底的从双向链中断开。其实在链中添加与删除操作与LinkedList是一样的，可以参考《Java集合框架之LinkedList及ListIterator实现源码分析 》
5、Hashtable和HashMap的区别：
Hashtable中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。在多线程应用程序中，我们应该使用Hashtable；而对于HashMap，则需要额外的同步机制。但HashMap的同步问题可通过Collections的一个静态方法得到解决：Map Collections.synchronizedMap(Map m)，当然与可以自己在使用地方加锁。
在HashMap中，可以允许null作为键，且只可以有一个，否则覆盖，但可以有一个或多个值为null。因为当get()方法返回null值时，即可以表示 HashMap中没有该键，也可以表示该键所对应的值为null，所以HashMap不能由get()方法来判断否存在某个键，而应该用containsKey()方法来判断；而Hashtable不允许null键与null值。
HashTable使用Enumeration，HashMap使用Iterator。
Hashtable是Dictionary的子类，HashMap是Map接口的一个实现类；
HashTable中hash table数组默认大小是11，增加的方式是 int newCapacity = oldCapacity /* 2 + 1;,即增加至2倍（而不是2倍加1，因为扩容是在增加元素前进行的，在扩容后会将新增元素放入容器中）。HashMap中hash数组的默认大小是16，而且一定是2的多少次方;另外两者的默认负载因子都是0.75。
求哈希地址与哈希地址转hash数组（Entry table[]）索引方法不同：
HashTable直接使用对象的hashCode：
Java代码
- int hash = key.hashCode();//直接使用键的hashCode方法求哈希值
- //哈希地址转hash数组索引，先使用最大正int数与，这样将负转正数，再与数组长度求模得到存入的hash数组索引位置
- int index = (hash & 0x7FFFFFFF) % tab.length;
int hash = key.hashCode();//直接使用键的hashCode方法求哈希值
//哈希地址转hash数组索引，先使用最大正int数与，这样将负转正数，再与数组长度求模得到存入的hash数组索引位置 int index = (hash & 0x7FFFFFFF) % tab.length;
而HashMap重新计算hash值，而且用位运算&代替求模：
Java代码
- int hash = hash(k);
- int i = indexFor(hash, table.length);
- static int hash(Object x) {
- //以键本身的hash码为基础求哈希地址，但看不懂是什么意思
- int h = x.hashCode();
- h += ~(h << 9);
- h ^= (h >>> 14);
- h += (h << 4);
- h ^= (h >>> 10);
- return h;
- }
- static int indexFor(int h, int length) {
- return h & (length-1);//将哈希地址转换成哈希数组中存入的索引号
- }
int hash = hash(k);
int i = indexFor(hash, table.length);
static int hash(Object x) { //以键本身的hash码为基础求哈希地址，但看不懂是什么意思
int h = x.hashCode(); h += ~(h << 9);
h ^= (h >>> 14); h += (h << 4);
h ^= (h >>> 10); return h;
} static int indexFor(int h, int length) {
return h & (length-1);//将哈希地址转换成哈希数组中存入的索引号 }
HashMap实现图：
6、集合中键值是否允许null小结
- List：可以有多个null，可以有重复值。
- HashSet：能插入一个null（因为内部是以 HashMap实现 ），忽略不插入重复元素。
- TreeSet：不能插入null （因为内部是以 TreeMap 实现 ） ，元素不能重复，如果待插入的元素存在，则忽略不插入，对元素进行排序。
- HashMap：允许一个null键与多个null值，若重复键，则覆盖以前值。
- TreeMap：不允许null键(实际上可以插入一个null键，如果这个Map里只有一个元素是不会报错的，因为一个元素时没有进行排序操作，也就不会报空指针异常，但如果插入第二个时就会立即报错)，但允许多个null值，覆盖已有键值。
- HashTable：不允许null键与null值(否则运行进报空指针异常)。也会覆盖以重复值。基于线程同步。
7、对List的选择：
- 对于随机查询与迭代遍历操作，数组比所有的容器都要快。
- 从中间的位置插入和删除元素，LinkedList要比ArrayList快，特别是删除操作。
- Vector通常不如ArrayList快，则且应该避免使用，它目前仍然存在于类库中的原因是为了支持过去的代码。
- 最佳实践：将ArrayList作为默认首选，只有当程序的性能因为经常从list中间进行插入和删除而变差的时候，才去选择LinkedList。当然了，如果只是使用固定数量的元素，就应该选择数组了。
8、对Set的选择：
- HashSet的性能总比TreeSet好(特别是最常用的添加和查找元素操作)。
- TreeSet存在的唯一原因是，它可以维持元素的排序状态，所以只有当你需要一个排好序的Set时，才应该使用TreeSet。
- 对于插入操作，LinkedHashSet比HashSet略微慢一点：这是由于维护链表所带来额外开销造成的。不过，因为有了链表，遍历LinkedHashSet会比HashSet更快。
9、对Map的选择：
- Hashtable和HashMap的效率大致相同(通常HashMap更快一点，所以HashMap有意取代Hashtable)。
- TreeMap通常比HashMap慢，因为要维护排序。
- HashMap正是为快速查询而设计的。
- LinkedHashMap比HashMap慢一点，因为它维护散列数据结构的同时还要维护链表。
10、Stack基于线程安全，Stack类是用Vector来实现的(public class Stack extends Vector)，但最好不要用集合API里的这个实现栈，因为它继承于Vector，本就是一个错误的设计，应该是一个组合的设计关系。
11、Iterator对ArrayList(LinkedList)的操作限制：
- 刚实例化的迭代器如果还没有进行后移(next)操作是不能马上进行删除与修改操作的。
- 可以用ListIterator对集合连续添加与修改，但不能连续删除。
- 进行添加操作后是不能立即进行删除与修改操作的。
- 进行删除操作后可以进行添加，但不能进行修改操作。
- 进行修改后是可以立即进行删除与添加操作的。
12、当以自己的对象做为HashMap、HashTable、LinkedHashMap、HashSet 、LinkedHashSet 的键时，一定要重写hashCode ()与equals ()方法，因为Object的hashCode()是返回内存地址，且equals()方法也是比较内存地址，所以当要在这些hash集合中查找时，如果是另外new出的新对象是查不到的，除非重写这两个方法。因为AbstractMap类的containsKey(Object key)方法实现如下：
Java代码
- if (e.hash == hash && eq(k, e.key))//先比对hashcode，再使用equals
- return true;
- static boolean eq(Object x, Object y) {
- return x == y || x.equals(y);
- }
if (e.hash == hash && eq(k, e.key))//先比对hashcode，再使用equals
return true;
static boolean eq(Object x, Object y) { return x == y || x.equals(y);
}
String对象是可以准确做为键的，因为已重写了这两个方法。
因此，Java中的集合框架中的哈希是以一个对象查找另外一个对象，所以重写hasCode与equals方法很重要。 13、重写hashCode()与equals()这两个方法是针对哈希类，至于其它集合，如果要用public boolean contains(Object o)或containsValue(Object value)查找时，只需要实现equals()方法即可，他们都只使用对象的 equals方法进行比对，没有使用 hashCode方法。 14、TreeMap/TreeSet：放入其中的元素一定要具有自然比较能力(即要实现java.lang.Comparable接口)或者在构造TreeMap/TreeSet时传入一个比较器(实现java.util.Comparator接口)，如果在创建时没有传入比较器，而放入的元素也没有自然比较能力时，会出现类型转换错误(因为在没有较器时，会试着转成Comparable型)。
两种比较接口：
Java代码
- //自然比较器
- public interface java.lang.Comparable {
- public int compareTo(Object o);
- }
- public interface java.util.Comparator {
- int compare(Object o1, Object o2);
- boolean equals(Object obj);
- }
//自然比较器
public interface java.lang.Comparable { public int compareTo(Object o);
}
public interface java.util.Comparator { int compare(Object o1, Object o2);
boolean equals(Object obj);
}
15、Collection或Map的同步控制：可以使用Collections类的相应静态方法来包装相应的集合类，使他们具线程安全，如publicstatic Collection synchronizedCollection (Collection c)方法实质返回的是包装后的SynchronizedCollection子类，当然你也可以使用Collections的synchronizedList、synchronizedMap、synchronizedSet方法来获取不同的经过包装了的同步集合，其代码片断：
Java代码
- public class Collections {
- //...
- static Collection synchronizedCollection(Collection c, Object mutex) {
- return new SynchronizedCollection(c, mutex);
- }
- public static List synchronizedList(List list) {
- //...
- }
- static Set synchronizedSet(Set s, Object mutex) {
- //...
- }
- public static Map synchronizedMap(Map m) {
- return new SynchronizedMap(m);
- }
- //...
- static class SynchronizedCollection implements Collection, Serializable {
- Collection c; // 对哪个集合进行同步（包装）
- Object mutex; // 对象锁，可以自己设置
- //...
- SynchronizedCollection(Collection c, Object mutex) {
- this.c = c;
- this.mutex = mutex;
- }
- public int size() {
- synchronized (mutex) {
- return c.size();
- }
- }
- public boolean isEmpty() {
- synchronized (mutex) {
- return c.isEmpty();
- }
- }
- //...
- }
- static class SynchronizedList extends SynchronizedCollection implements List {
- List list;
- SynchronizedList(List list, Object mutex) {
- super(list, mutex);
- this.list = list;
- }
- public Object get(int index) {
- synchronized (mutex) {
- return list.get(index);
- }
- }
- //...
- }
- static class SynchronizedSet extends SynchronizedCollection implements Set {
- SynchronizedSet(Set s) {
- super(s);
- }
- //...
- }
- //...
- }
public class Collections {
//...
static Collection synchronizedCollection(Collection c, Object mutex) {
return new SynchronizedCollection(c, mutex);
}
public static List synchronizedList(List list) {
//...
}
static Set synchronizedSet(Set s, Object mutex) {
//...
}
public static Map synchronizedMap(Map m) {
return new SynchronizedMap(m);
}
//...
static class SynchronizedCollection implements Collection, Serializable {
Collection c; // 对哪个集合进行同步（包装）
Object mutex; // 对象锁，可以自己设置
//...
SynchronizedCollection(Collection c, Object mutex) {
this.c = c;
this.mutex = mutex;
}
public int size() {
synchronized (mutex) {
return c.size();
}
}
public boolean isEmpty() {
synchronized (mutex) {
return c.isEmpty();
}
}
//...
}
static class SynchronizedList extends SynchronizedCollection implements List {
List list;
SynchronizedList(List list, Object mutex) {
super(list, mutex);
this.list = list;
}
public Object get(int index) {
synchronized (mutex) {
return list.get(index);
}
}
//...
}
static class SynchronizedSet extends SynchronizedCollection implements Set {
SynchronizedSet(Set s) {
super(s);
}
//...
}
//...
}
由包装的代码可以看出只是把原集合的相应方法放在同步块里调用罢了。
16、通过迭代器修改集合结构
在使用迭代器遍历集合时，我们不能通过集合本身来修改集合的结构（添加、删除），只能通过迭代器来操作，下面是拿对HashMap删除操作的测试，其它集合也是这样：
Java代码
- public static void main(String[] args) {
- Map map = new HashMap();
- map.put(1, 1);
- map.put(2, 3);
- Set entrySet = map.entrySet();
- Iterator it = entrySet.iterator();
- while (it.hasNext()) {
- Entry entry = (Entry) it.next();
- //*
- /* 可以通过迭代器来修改集合结构，但前提是要在已执行过 next 或
- /* 前移操作，否则会抛异常：IllegalStateException
- /*/
- // it.remove();
- //*
- /* 抛异常：ConcurrentModificationException 因为通过 迭代 器操
- /* 作时，不能使用集合本身来修
- /* 改集合的结构
- /*/
- // map.remove(entry.getKey());
- }
- System.out.println(map);
- }
public static void main(String[] args) {
Map map = new HashMap(); map.put(1, 1);
map.put(2, 3); Set entrySet = map.entrySet();
Iterator it = entrySet.iterator(); while (it.hasNext()) {
Entry entry = (Entry) it.next(); //*
/ 可以通过迭代器来修改集合结构，但前提是要在已执行过 next 或 / 前移操作，否则会抛异常：IllegalStateException
/*/ // it.remove();
// / 抛异常：ConcurrentModificationException 因为通过 迭代 器操
/ 作时，不能使用集合本身来修 / 改集合的结构
/*/ // map.remove(entry.getKey());
} System.out.println(map);
}
Hash表分析以及Java实现
Posted onHash表分析以及Java实现
java-mzd
永久域名 http://java-mzd.iteye.com
2010-11-29
Hash表分析以及Java实现
文章分类:综合技术 这篇博客主要探讨Hash表中的一些原理/概念，及根据这些原理/概念，自己设计一个用来存放/查找数据的Hash表，并且与JDK中的HashMap类进行比较。
我们分一下七个步骤来进行。
一。 **Hash**表概念
二 . **Hash**构造函数的方法，及适用范围
三.** Hash处理冲突方法，各自特征**
四.** Hash查找过程**
五.** 实现一个使用Hash存数据的场景-------Hash**查找算法，插入算法
六.** JDK中HashMap的实现**
七.** Hash表与HashMap的对比，性能分析**
一。 **Hash**表概念
在查找表中我们已经说过，在Hash表中，**记录在表中的位置和其关键字之间存在着一种确定的关系**。这样 我们就能预先知道所查关键字在表中的位置，从而直接通过下标找到记录。使ASL趋近与0.
1) ** **哈希(Hash)函数是一个映象，即： 将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地 址集合的大小不超出允许范围即可；
2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1¹ key2，而 f (key1) = f(key2)。
3). 只能尽量减少冲突而不能完全避免冲突，这是因为通常关键字集合比较大，其元素包括所有可能的关键字， 而地址集合的元素仅为哈希表中的地址值
在构造这种特殊的“查找表” 时，除了需要选择一个**“好”(尽可能少产生冲突)**的哈希函数之外；还需要找到一 种**“处理冲突”** 的方法。
二 . **Hash**构造函数的方法，及适用范围
- 直接定址法
- 数字分析法
- 平方取中法
- 折叠法
- 除留余数法
- 随机数法
（1）直接定址法：
哈希函数为关键字的线性函数，H(key) = key 或者 H(key) = a ´ key + b
**此法仅适合于**：地址集合的大小 = = 关键字集合的大小，其中a和b为常数。
（2）数字分析法：
假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为地址。
**此法适于:**能预先估计出全体关键字的每一位上各种数字出现的频度。
（3）平方取中法：
以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同 时平方值的中间各位又能受到整个关键字中各位的影响。
**此法适于:**关键字中的每一位都有某些数字重复出现频度很高的现象。
（4）折叠法：
将关键字分割成若干部分，然后取它们的叠加和为哈希地址。两种叠加处理的方法：移位叠加:将分 割后的几部分低位对齐相加；间界叠加:从一端沿分割界来回折叠，然后对齐相加。
**此法适于：**关键字的数字位数特别多。
（5）除留余数法：
设定哈希函数为:H(key) = key MOD p ( p≤m )，其中， m为表长，p 为不大于 m 的素数，或 是不含 20 以下的质因子
（6）随机数法：
设定哈希函数为:H(key) = Random(key)其中，Random 为伪随机函数
**此法适于：**对长度不等的关键字构造哈希函数。
实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，以及哈希表 长度（哈希地址范围），**总的原则是使产生冲突的可能性降到尽可能地小。**
三.** Hash处理冲突方法，各自特征**
“**处理冲突”的实际含义是：为产生冲突的关键字寻找下一个哈希地址。**
- **开放定址法**
- **再哈希法**
- **链地址法**
（1）开放定址法：
为产生冲突的关键字地址 H(key) 求得一个地址序列： H0, H1, H2, …, Hs 1≤s≤m-1，Hi = ( H(key) +di ) MOD m，其中： i=1, 2, …, s，H(key)为哈希函数;m为哈希表长;
（2）链地址法：
将所有哈希地址相同的记录都链接在同一链表中。
（3）再哈希法：
方法：构造若干个哈希函数，当发生冲突时，根据另一个哈希函数计算下一个哈希地址，直到冲突不再发 生。即：Hi=Rhi(key) i=1,2,……k，其中：Rhi——不同的哈希函数，特点：计算时间增加****
四.** Hash查找过程**
对于给定值 K,计算哈希地址 i = H(K)，若 r[i] = NULL 则查找不成功，若 r[i].key = K 则查找成功， 否则 “求 下一地址 Hi” ，直至r[Hi] = NULL (查找不成功) 或r[Hi].key = K (查找成功) 为止。
五.** 实现一个使用Hash存数据的场景-------Hash**查找算法，插入算法
假设我们要设计的是一个用来保存中南大学所有在校学生个人信息的数据表。因为在校学生数量也不是特别巨大(8W?)，每个学生的学号是唯一的,因此，我们可以简单的应用直接定址法，声明一个10W大小的数组，每个学生的学号作为主键。然后每次要添加或者查找学生，只需要根据需要去操作即可。
但是，显然这样做是**很脑残**的。这样做系统的可拓展性和复用性就非常差了，比如有一天人数超过10W了？如果是用来保存别的数据呢？或者我只需要保存20条记录呢？声明大小为10W的数组显然是太浪费了的。
如果我们是用来保存大数据量（比如银行的用户数，4大的用户数都应该有3-5亿了吧？），这时候我们计算出来的HashCode就很可能会有冲突了， 我们的系统应该有“处理冲突”的能力，此处我们**通过挂链法“处理冲突”**。
如果我们的数据量非常巨大，并且还持续在增加，如果我们仅仅只是通过挂链法来处理冲突，可能我们的链上挂了上万个数据后，这个时候再通过静态搜索来查找链表，显然性能也是非常低的。所以我们的系统应该还能实现自动扩容，**当容量达到某比例后，即自动扩容，使装载因子保存在一个固定的水平上**。
综上所述，我们对这个Hash容器的基本要求应该有如下几点：
**满足Hash表的查找要求（废话）**
能支持从小数据量到大数据量的自动转变（自动扩容）
使用挂链法解决冲突
好了，既然都分析到这一步了，咱就闲话少叙，直接开始上代码吧。
Java代码
- package cn.javamzd.collection.search;
- public class MyMap
- private int size;// 当前容量
- private static int INIT_CAPACITY = 16;// 默认容量
- private Entry
- private static float LOAD_FACTOR = 0.75f;// 装载因子
- private int max;// 能存的最大的数=capacity/*factor
- // 自己设置容量和装载因子的构造器
- public MyMap(int init_Capaticy, float load_factor) {
- if (init_Capaticy < 0)
- throw new IllegalArgumentException("Illegal initial capacity: "
- init_Capaticy);
- if (load_factor <= 0 || Float.isNaN(load_factor))
- throw new IllegalArgumentException("Illegal load factor: "
- load_factor);
- this.LOAD_FACTOR = load_factor;
- max = (int) (init_Capaticy /* load_factor);
- container = new Entry[init_Capaticy];
- }
- // 使用默认参数的构造器
- public MyMap() {
- this(INIT_CAPACITY, LOAD_FACTOR);
- }
- ///
- /* 存
- /*
- /* @param k
- /* @param v
- /* @return
- /*/
- public boolean put(K k, V v) {
- // 1.计算K的hash值
- // 因为自己很难写出对不同的类型都适用的Hash算法，故调用JDK给出的hashCode()方法来计算hash值
- int hash = k.hashCode();
- //将所有信息封装为一个Entry
- Entry
- if(setEntry(temp, container)){
- // 大小加一
- size++;
- return true;
- }
- return false;
- }
- ///
- /* 扩容的方法
- /*
- /* @param newSize
- /* 新的容器大小
- /*/
- private void reSize(int newSize) {
- // 1.声明新数组
- Entry
- max = (int) (newSize /* LOAD_FACTOR);
- // 2.复制已有元素,即遍历所有元素，每个元素再存一遍
- for (int j = 0; j < container.length; j++) {
- Entry
- //因为每个数组元素其实为链表，所以…………
- while (null != entry) {
- setEntry(entry, newTable);
- entry = entry.next;
- }
- }
- // 3.改变指向
- container = newTable;
- }
- ///
- /*将指定的结点temp添加到指定的hash表table当中
- /* 添加时判断该结点是否已经存在
- /* 如果已经存在，返回false
- /* 添加成功返回true
- /* @param temp
- /* @param table
- /* @return
- /*/
- private boolean setEntry(Entry
- // 根据hash值找到下标
- int index = indexFor(temp.hash, table.length);
- //根据下标找到对应元素
- Entry
- // 3.若存在
- if (null != entry) {
- // 3.1遍历整个链表，判断是否相等
- while (null != entry) {
- //判断相等的条件时应该注意，除了比较地址相同外，引用传递的相等用equals()方法比较
- //相等则不存，返回false
- if ((temp.key == entry.key||temp.key.equals(entry.key)) && temp.hash == entry.hash&&(temp.value==entry.value||temp.value.equals(entry.value))) {
- return false;
- }
- //不相等则比较下一个元素
- else if (temp.key != entry.key && temp.value != entry.value) {
- //到达队尾，中断循环
- if(null==entry.next){
- break;
- }
- // 没有到达队尾，继续遍历下一个元素
- entry = entry.next;
- }
- }
- // 3.2当遍历到了队尾，如果都没有相同的元素，则将该元素挂在队尾
- addEntry2Last(entry,temp);
- }
- // 4.若不存在,直接设置初始化元素
- setFirstEntry(temp,index,table);
- return true;
- }
- private void addEntry2Last(Entry
- if (size > max) {
- reSize(container.length /* 4);
- }
- entry.next=temp;
- }
- ///
- /* 将指定结点temp，添加到指定的hash表table的指定下标index中
- /* @param temp
- /* @param index
- /* @param table
- /*/
- private void setFirstEntry(Entry
- // 1.判断当前容量是否超标，如果超标，调用扩容方法
- if (size > max) {
- reSize(table.length /* 4);
- }
- // 2.不超标，或者扩容以后，设置元素
- table[index] = temp;
- //！！！！！！！！！！！！！！！
- //因为每次设置后都是新的链表，需要将其后接的结点都去掉
- //NND，少这一行代码卡了哥哥7个小时（代码重构）
- temp.next=null;
- }
- ///
- /* 取
- /*
- /* @param k
- /* @return
- /*/
- public V get(K k) {
- Entry
- // 1.计算K的hash值
- int hash = k.hashCode();
- // 2.根据hash值找到下标
- int index = indexFor(hash, container.length);
- // 3。根据index找到链表
- entry = container[index];
- // 3。若链表为空，返回null
- if (null == entry) {
- return null;
- }
- // 4。若不为空，遍历链表，比较k是否相等,如果k相等，则返回该value
- while (null != entry) {
- if (k == entry.key||entry.key.equals(k)) {
- return entry.value;
- }
- entry = entry.next;
- }
- // 如果遍历完了不相等，则返回空
- return null;
- }
- ///
- /* 根据hash码，容器数组的长度,计算该哈希码在容器数组中的下标值
- /*
- /* @param hashcode
- /* @param containerLength
- /* @return
- /*/
- public int indexFor(int hashcode, int containerLength) {
- return hashcode & (containerLength - 1);
- }
- ///
- /* 用来实际保存数据的内部类,因为采用挂链法解决冲突，此内部类设计为链表形式
- /*
- /* @param
key - /* @param
- /* value
- /*/
- class Entry
- Entry
- K key;// key
- V value;// value
- int hash;// 这个key对应的hash码，作为一个成员变量，当下次需要用的时候可以不用重新计算
- // 构造方法
- Entry(K k, V v, int hash) {
- this.key = k;
- this.value = v;
- this.hash = hash;
- }
- //相应的getter()方法
- }
- }
package cn.javamzd.collection.search; public class MyMapkey / @param/ value // class Entry
代码中有相当清楚的注释了
在文章的最后这里，我要强烈的宣泄下感情
MLGBD，本来以为分析的挺到位了，写出这个东西也就最多需要个把小时吧
结果因为通宵作业，脑袋运转不灵
硬是花了哥三个小时才写出了
好不容易些出来了
我日
看着代码比较混乱
然后就对代码重构了下
把逻辑抽象清楚，进行重构就花了个多小时
好不容易构造好了
就开始了TMD的一直报错了----------大数据量测试时到大概5000就死循环了
各种调试，各种分析都觉得没错误
最后花了哥7个小时终于找出来了
我擦
第一次初始化加的时候，因为每个元素的next都是空的
而扩充容量resize()时，因为冲突处理是链式结构的
当将他们重新hash添加的时候，重复的这些鸟元素的next是有元素的
一定要设置为null
七.性能分析：
1.因为冲突的存在，其查找长度不可能达到O(1)
2哈希表的平均查找长度是装载因子a 的函数，而不是 n 的函数。
3.用哈希表构造查找表时，可以选择一个适当的装填因子 ，使得平均查找长度限定在某个范围内。
最后给出我们这个HashMap的性能
测试代码
Java代码
- public class Test {
- public static void main(String[] args) {
- MyMap
- Long aBeginTime=System.currentTimeMillis();//记录BeginTime
- for(int i=0;i<1000000;i++){
- mm.put(""+i, ""+i/*100);
- }
- Long aEndTime=System.currentTimeMillis();//记录EndTime
- System.out.println("insert time-->"+(aEndTime-aBeginTime));
- Long lBeginTime=System.currentTimeMillis();//记录BeginTime
- mm.get(""+100000);
- Long lEndTime=System.currentTimeMillis();//记录EndTime
- System.out.println("seach time--->"+(lEndTime-lBeginTime));
- }
}
public class Test { public static void main(String[] args) { MyMap100W个数据时，全部存储时间为1S多一点，而搜寻时间为0
insert time-->1536 seach time--->0
好了，牢骚发完了
本来今天想写个有关大访问量处理的一些基本概念的文章
全泡汤了,明天写吧
8 顶3 踩 简单Spring容器实现 | 查找表分析（总论）
- 01:46
- 浏览 (854)
- 评论 (8)
- 分类: 数据结构----------JAVA类集
- 相关推荐
评论
8 楼 dengyi04405 2010-12-16 引用
错了...是mm.get(""+36309) 为null，在最后resize的时候挂在9的一起，然后丢失了。 setEntry(entry, newTable); ----entry在first时next=null entry = entry.next;---永远是null 7 楼 dengyi04405 2010-12-16 引用
resize()好像还是有bug，挂在一个链地址下的数据resize时只能取出第一个，后面的数据就丢失了。
for(int i=0;i<90000;i++) 循环后mm.get(""+100000) 是null
不知道是不是，楼主看看
heng_aa 写道
无聊又测了一下，死循环是因为while没有这种情况的判断，我是加上这些代码的：
else if(temp.key == entry.key && temp.value != entry.value) {
entry.value = temp.value;
return true;
}
还有我查找不到数据，应该是在109行那里少加了这句吧，return true;因为没有这句下面的setFirstEntry(temp,index,table); 还会执行。
看看是不是这样！！！
恩~~确实需要加上这个判断~
不然当传入相同的key不同的value的时候，不会覆盖掉原理的value
这时候linked里面就会有相同的key，不同的value，后面那个value就没意义了。
只是，这样还是没有死循环吖。。囧
恩，无论如何，这个BUG是确实需要改进的。
5 楼 heng_aa 2010-11-30 引用
无聊又测了一下，死循环是因为while没有这种情况的判断，我是加上这些代码的：
else if(temp.key == entry.key && temp.value != entry.value) {
entry.value = temp.value;
return true;
}
还有我查找不到数据，应该是在109行那里少加了这句吧，return true;因为没有这句下面的setFirstEntry(temp,index,table); 还会执行。
看看是不是这样！！！
heng_aa 写道
我测试了一下，发现几个问题。如果放入相同的key不同的value,程序就死循环了！还有扩容后，indexFor（）的算值就不同了，也就是说通过这个算法查找不到值了。无聊试一下而已，不过我也学到了不少东西，看这些问题能不能改进？？ 谢谢提醒哦 分几点分析吧 扩容后，通过indexFor()计算的值肯定是需要变化的啊，因为这个时候计算规则变了啊 需要把每个元素重新散列到数组里去啊，这时候通过get()再取的时候，计算的时候，indexFor()是按照新的数组大小来的，所以肯定还是能找到的啊 至于死循环的问题，在重构代码前我测试是正常的，重构后忘了测试这个问题了。。 囧。。。等晚上再测试下再回答你吧。 3 楼 heng_aa 2010-11-30 引用
我测试了一下，发现几个问题。如果放入相同的key不同的value,程序就死循环了！还有扩容后，indexFor（）的算值就不同了，也就是说通过这个算法查找不到值了。无聊试一下而已，不过我也学到了不少东西，看这些问题能不能改进？？
smithfox 写道
好文，对动态大数据量的Hash处理很有用. 幸苦了，注意身体呀! 多谢关照~~ 1 楼 smithfox 2010-11-29 引用
好文，对动态大数据量的Hash处理很有用. 幸苦了，注意身体呀!
发表评论
表情图标
字体颜色: 标准深红红色橙色棕色黄色绿色橄榄青色蓝色深蓝靛蓝紫色灰色白色黑色 字体大小: 标准1 (xx-small)2 (x-small)3 (small)4 (medium)5 (large)6 (x-large)7 (xx-large) 对齐: 标准居左居中居右
提示：选择您需要装饰的文字, 按上列按钮即可添加上相应的标签
您还没有登录，请登录后发表评论(快捷键 Alt+S / Ctrl+Enter)
java_mzd
搜索本博客
最近访客 >>更多访客
博客分类
- 全部博客 (43)
- 数据结构----------JAVA类集 (5)
-
我的留言簿 >>更多留言
楼主 你工作多久了。。。。 -- by fanmingxing
- 写的不错，学习，谢谢！ -- by chenge2k
- 看了LZ的文章，发现工作快两年的我，就像是一块浮起来的木头，真的很惭愧！也不怪我拿 ... -- by GoTiger
其他分类
存档
- 2011-05 (2)
- 2011-04 (7)
- 2011-03 (2)
-
评论排行榜
- TCP/IP传输层，你懂多少？
- 淘宝武汉/*面试归来
- 淘宝、金山网络，百感交集
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。若作者同意转载，必须以超链接形式标明文章原始出处和作者。 © 2003-2011 ITeye.com. All rights reserved. [ 京ICP证110151号 ]
DWR如何获得返回对象 list Map Set list
Posted onDWR如何获得返回对象 list Map Set list
DWR**如何获得返回对象**list Map Set list.add(JavaBean)
1**、调用没有返回值和参数的JAVA方法**
1.1、dwr.xml的配置
标签指定要公开给javascript的java类名。
其中TestClass.js是dwr根据配置文件自动生成的，engine.js和util.js是dwr自带的脚本文件。 其次，编写调用java方法的javascript函数 Function callTestMethod1(){ testClass.testMethod1(); } 2**、调用有简单返回值的java方法**
2.1**、dwr.xml的配置**配置同1.1
3**、调用有简单参数的java方法**
3.1**、dwr.xml的配置**配置同1.1
4**、调用返回JavaBean的java方法4.1、dwr.xml的配置**
<convert converter="bean" match=""com.dwr.TestBean">
5**、调用有JavaBean参数的java方法5.1、dwr.xml的配置 **配置同4.1
6**、调用返回List、Set或者Map的java方法6.1、dwr.xml的配置**配置同4.1
注意：如果List、Set或者Map中的元素均为简单类型（包括其封装类）或String、Date、数组和集合类型，则不需要
7**、调用有List、Set或者Map参数的java方法**
7.1**、dwr.xml的配置**
======================================================================================
DWR**根据dwr.xml生成和Java代码类似的Javascript代码。**
相对而言Java同步调用，创建与Java代码匹配的Ajax远程调用接口的最大挑战来至与实现Ajax的异步调用特性。
DWR**通过引入回调函数来解决这个问题，当结果被返回时，DWR会调用这个函数。**
有两种推荐的方式来使用DWR实现远程方法调用。可以通过把回调函数放在参数列表里，也可以把回调函数放到元数据对象里。
当然也可以把回调函数做为第一个参数，但是不建议使用这种方法。因为这种方法在处理自动处理http对象时(查看"Alternative Method")上会有问题。这个方法主要是为向下兼容而存在的。
假设你有一个这样的Java方法：
public class Remote { public String getData(int index) { ... }}
我们可以在Javascript中这样使用：
...function handleGetData(str) { alert(str);}Remote.getData(42, handleGetData);
42**是Java方法getData()的一个参数。**
此外你也可以使用这种减缩格式：
Remote.getData**(42, function(str) { alert(str); });**
另外一种语法时使用"调用元数据对象"来指定回调函数和其他的选项。上面的例子可以写成这样：
Remote.getData**(42, { callback:function(str) { alert(str); }});**
这种方法有很多优点：易于阅读，更重要的指定额外的调用选项。
在回调函数的元数据中你可以指定超时和错误的处理方式。例如：
Remote.getData**(42, { callback:function(str) { alert(str); }, timeout:5000, errorHandler:function(message) { alert("Oops: " + message); }});**
有些情况下我们很难区分各种回调选项(记住，Javascript是不支持函数重载的)。例如：
Remote.method**({ timeout:3 }, { errorHandler:somefunc });**
这两个参数之一是bean的参数，另一个是元数据对象，但是我们不能清楚的告诉DWR哪个是哪个。为了可以跨浏览器，我们假定null == undefined。 所以当前的情况，规则是：
- 如果第一个或最后一个是一个函数，那么它就是回调函数，没有元数据对象，并且其他参数都是Java的方法参数。
- 另外，如果最后一个参数是一个对象，这个对象中有一个callback成员，并且它是个函数，那么这个对象就是元数据对象，其他的都是Java方法参数。
- 另外，如果第一个参数是 null ，我们就假设没有回调函数，并且其他的都是Java方法参数。尽管如此，我们会检查最后一个参数是不是null，如果是就发出警告。
- 最后如果最后一个参数是null，那么就没有callback函数。
- 另外，发出错误信号是个糟糕的请求格式。
假设你有这样的Java方法：
public class Remote { public void setPerson(Person p) { this.person = p; }}
Person**对象的结构是这样的：**
public Person { private String name; private int age; private Date[] appointments; // getters and setters ...}
那么你可以在Javascript中这样写：
var**p = { name:"Fred Bloggs", age:42, appointments:[ new Date(), new Date("1 Jan 2008") ]};Remote.setPerson(p);**
在Javascript没有出现的字段，在Java中就不会被设置。
因为setter都是返回'void'，我们就不需要使用callback函数了。如果你想要一个返回void的服务端方法的完整版，你也可以加上callback函数。很明显DWR不会向它传递任何参数。
AD系统安装配置指南(JAVA
Posted onAD系统安装配置指南(JAVA-JNDI-LDAP-Exchange)
xsailer的专栏
#
*
用户操作[留言] [发消息] [加为好友] 订阅我的博客
[编辑]xsailer的公告技术杂志[编辑]文章分类*
EAI
Hibernate
HTML/JAVASCRIPT
IDE
J2EE
JAVA
JSP
LDAP
SOA
SQL
安全认证
测试
程序人生
电子政务
读书
工作流
开源框架
容器
软件工程
算法
网络
系统架构
项目管理
邮件[编辑]BLOGjava.sun大家一起学习交流吧子在川上曰守望破法月光博客砖头胡长城（银狐999）BLOG萧风瑟瑟－筱梓阿朱软件坊[编辑]javaIBM技术Java 中文网址大全JAVA学习室SQLUS频道[编辑]常用网站安徽省图书馆[编辑]手册DHTML 对象WebLogic Server 性能及调整管理控制台联机帮助[编辑]邮件小专题：常用的邮件系统优劣分析存档* 2010年02月(1)
- 2009年09月(2)
- 2008年08月(2)
- 2008年07月(3)
- 2008年06月(3)
- 2008年05月(6)
- 2008年04月(6)
- 2008年03月(4)
- 2008年02月(8)
- 2008年01月(5)
- 2007年12月(3)
- 2007年11月(10)
- 2007年10月(14)
- 2007年09月(6)
- 2007年08月(12)
- 2007年07月(4)
- 2007年06月(25)
- 2007年05月(7)
- 2007年04月(9)
- 2007年03月(10)
- 2007年02月(9)
- 2005年10月(1)
AD系统安装配置指南(JAVA-JNDI-LDAP-Exchange) 收藏
JAVA技术 /billzw 发表于2006-08-02
- 概述 当前解决的途径如下： 采用Java的JNDI通过LDAP协议去操作AD(Windows 2000 Server Active Directory的简称，下同)，实现用户和密码与OA系统同步。用户登陆OA系统时，同时登陆mail。 这样就实现的单点登陆。
- M$ Active Directory安装 在独立服务器上安装 Windows 2000 Server 或 Windows 2000 Advanced Server 之后，运行"Active Directory 向导"以创建新的 Active Directory 目录林或域，并将 Windows 2000 服务器转换为目录林中的第一个域控制器 (DC)。若要将 Windows 2000 服务器转换为目录林中第一个域控制器，请按照下列步骤操作：
- 将 Windows 2000 光盘插入光驱中。
- 单击开始，单击运行，然后键入 dcpromo。
- 单击确定以启动 Active Directory 安装向导，然后单击下一步。
- 单击新域的域控制器，然后单击下一步。
- 单击创建一个新的域目录树，然后单击下一步。
- 单击创建新的域目录林，然后单击下一步。
- 为新的 Active Directory 指定完整的 DNS 名称。如：mail.yuanling.gov.cn单击下一步。
- 接受域的默认 NetBIOS 名（如：yuanlingmail）。单击下一步。
- 将数据库和日志文件的位置设置为在默认设置 c:\winnt\ntds 文件夹下，然后单击下一步。
- 将 Sysvol 文件夹的位置设置为默认设置 c:\winnt\sysvol 文件夹，然后单击下一步。
- 单击安装和配置 DNS，然后单击下一步。
- 单击只与 Windows 2000 服务器相兼容的权限，然后单击下一步。
- 因这是实验室环境，将"目录服务恢复模式的管理员"密码留为空白。请注意，在完整的生产环境中，应通过使用安全密码格式进行设置。单击下一步。
- 检查并确认所选择的选项，然后单击下一步。
- 在安装 Active Directory 过程中，正在配置 Active Directory进度表出现。注意，该操作将需要几分钟。
- 出现提示时，重新启动计算机。计算机重新启动后，确认已经为新的域控制器创建了 DNS 服务位置记录。若要确认已创建 DNS 服务位置记录，请按照下列步骤操作：
- 检查DNS设置。 a. 单击开始，单击程序，单击管理工具，然后单击 DNS 以启动"DNS 管理"控制台。 b. 单击服务器名称，单击正向搜索区域，单击域名，然后展开该域。 c. 确认 _msdcs、_sites、_tcp 和 _udp 文件夹已存在。这些文件夹和它们包含的服务位置记录对于 Active Directory 和 Windows 2000 的运行至关重要。
- 安装企业根证书服务，并配置自动证书分配 参看在《中小型公司建立企业根证书颁发机构 (CA)》 http://www.microsoft.com/china/technet/security/sgk/build_ent_root_ca.mspx 此文中涉及到操作系统策略，请仔细对照。
安装M$ Exchange Server 参见《Exchange 2000 server的安装实录》。 注：Exchange安装完成后，会自动扩展M$ AD，新生成选择页。是”Exchange Genaral”和”Email Address”，见下图。
安装AD管理工具(可选,用于LDAP连接的测试) 1) 将Windows 2000 Server的光盘插入光驱; 2) 定位到 光盘:\SUPPORT\TOOLS目录,点击Setup.exe,进行安装; 3) 安装完成后,直接在命令提示符下运行 ldp 命令,即可打开AD管理工具;如下图
LDAP与SSL 1) 在IE中输入https://mail.yuanling.gov.cn:636，将弹出一个窗口，
2) 点击以后不现显示该警告，再点击确定，三四秒种后，将弹出一个客户身份验证窗口，
3) 点击确定，将弹出一个安全警报窗口
4) 点击“查看证书”，弹出证书窗口
5) 选择“详细信息”页，点击“复制到文件”
6) 这时，将启动“证书导出向导”，选择格式为“Base-64 encoded X.509 (.CER)”，将其导出到本地，如D：根目录下，命名为client.cer
7) 接下来的工作就是要将保存下来的证书存储到TrustStore中，我们这里要用keytool命令，这是JDK自带的，在运行keytool之前，必先安装JDK (我们采用的是JDK 1.4)，并确认JDK的bin目录已加设到path中。命令格式如下：keytool -import -keystore trustedcerts -alias yl -file client.cer 此时，生成了trustedcerts证书文件。
8) 完成
- 用CSVDE来导出AD中的信息 CSVDE也是AD管理工具中的一种。 在创建AD用户的同时，应当创建Exchange Server 的mailbox，这里要用到几个系统变量，需要从用CSVDE中导出的文件中查得。 命令格式：CSVDE -f csvde.csv 用Excel打开这个文件，找到homeMDB，homeMTA，msExchHomeServerName三个变量。在创建mailbox时应当用到。
package com.sunyard.sunoa.security.LDAP; …. public class ADConnection { …. String homeMDB = "CN=Mailbox Store (HA),CN=First Storage Group,CN=InformationStore,CN=HA,CN=Servers,CN=First Administrative Group,CN=Administrative Groups,CN=First Organization,CN=Microsoft Exchange,CN=Services,CN=Configuration,DC=hzyl,DC=com"; newAttributes.put(new BasicAttribute("homeMDB", homeMDB)); String homeMTA = "CN=Microsoft MTA,CN=HA,CN=Servers,CN=First Administrative Group,CN=Administrative Groups,CN=First Organization,CN=Microsoft Exchange,CN=Services,CN=Configuration,DC=hzyl,DC=com"; newAttributes.put(new BasicAttribute("homeMTA", homeMTA)); String msExchHomeServerName = "/o=First Organization/ou=First Administrative Group/cn=Configuration/cn=Servers/cn=HA"; newAttributes.put(new BasicAttribute("msExchHomeServerName", msExchHomeServerName)); ….
}
- 注意点 1) 系统部署的服务器如果与AD所在的服务器不是同一台，那么应当将系统所在的服务器的网卡DNS设置为AD或本网内的DNS服务器，使AD的域名可被解析到AD所在的服务器；如对DNS不了解，可先上微软网站去学习一下； 2) 系统中对连接AD的服务器地址指定一定要为域名，否则无法通过SSL的验证； 3) M$ AD不同于其他目录服务器，凡涉及到用户密码更新的都需要通过SSL。
发表于 @ 2007年04月24日 23:32:00 | 评论( loading... )| 编辑| 举报| 收藏
旧一篇:LDAP介绍 | 新一篇:JAVA读取AD信息
查看最新精华文章 请访问博客首页相关文章
Copyright © xsailerPowered by CSDN Blog
