Thinker

  - long way to go...

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  24 随笔 :: 0 文章 :: 143 评论 :: 0 Trackbacks
    我们知道ArrayList是基于Array的,所以它拥有Array的优点,适用于按索引取值的场合,但是它不适合插入数据和删除数据,因为每插入或删除一次就会产生一次大量数组内容Copy的操作。而LinkedList正好与ArrayList相反,它比较适合与插入删除操作,不适合于索引取值,因为它不可以像数组一样根据索引值直接就可以定位元素的地址,而需要从头至尾一个一个的来数位置。
    那么有没有一种数据结构既拥有数据索引取值快速的特性,又拥有快速删除元素的优点呢?当然有,下面我介绍的就是其中的一种方式,我称之为无序数组(概念可能与数组的概念有些冲突,因为数组本身是有序的),这种数组包装方法是基于数组的,所以拥有数组快速索引取值的特点;并且在删除元素的时候并不移动(Copy)数组内部元素,所以删除元素的时候速度很快。缺点就是损失了数组的有序性,同时因为该数组是无序的,所以没有必要提供数据中间插入操作,只可以向数据的末尾添加数据。
    这个数据结构的设计是基于效率的,所以它只适合于对数组的按索引取值和随机删除元素的效率要求都比较高,同时对数组的有序性(这里的有序性不是指数组元素的排序顺序,而是指数组元素的索引顺序)没有任何要求的场合。
     这个数据结构的一个使用示例场合就是随机取数据。可以用该数组存储数据源,然后随机生成一个索引,并将该索引对应的元素remove掉。而且还能保证数据不被重复读取。
    下面提供的示例代码抽取了这个数组的最基本功能,很清晰,没有什么需要解释的地方。导致数组无序和快速删除的根源就在于 remove(int index) 方法中,大家自己看吧。
  1 public class NoOrderArray
  2 {
  3   private Object[] values = null;
  4 
  5   private int size = 0;
  6 
  7   /**
  8    * 数组 NoOrderArray 的构造函数。 <br>
  9    * 
 10    * @param capacity int - 数组的初始容量。
 11    */
 12   public NoOrderArray(int capacity)
 13   {
 14     if (capacity < 0)
 15       throw new IllegalArgumentException("Illegal Capacity: " + capacity);
 16 
 17     values = new Object[capacity];
 18   }
 19 
 20   /**
 21    * 数组 NoOrderArray 的构造函数,初始容量为 8.<br>
 22    */
 23   public NoOrderArray()
 24   {
 25     this(10);
 26   }
 27 
 28   /**
 29    * 设定数组的容量大小,使其至少满足 minCapacity 所指的大小。 <br>
 30    * 
 31    * @param minCapacity int - 新的容量值。
 32    */
 33   public void ensureCapacity(int minCapacity)
 34   {
 35     int oldCapacity = values.length;
 36 
 37     if (minCapacity > oldCapacity)
 38     {
 39       Object[] oldValues = values;
 40 
 41       int newCapacity = (oldCapacity * 3/ 2 + 1;
 42 
 43       if (newCapacity < minCapacity)
 44         newCapacity = minCapacity;
 45 
 46       values = new Object[newCapacity];
 47 
 48       System.arraycopy(oldValues, 0, values, 0, size);
 49     }
 50   }
 51 
 52   /**
 53    * 向数组 NoOrderArray 中添加元素内容。 <br>
 54    * 
 55    * @param value - 添加的内容。
 56    */
 57   public void add(Object value)
 58   {
 59     ensureCapacity(size + 1);
 60 
 61     values[size] = value;
 62 
 63     size ++;
 64   }
 65 
 66   /**
 67    * 清除数组 NoOrderArray 中的全部元素。 <br>
 68    */
 69   public void clear()
 70   {
 71     // 释放内存
 72     for (int i = 0; i < size; i ++)
 73       values[i] = null;
 74 
 75     size = 0;
 76   }
 77 
 78   /**
 79    * 返回数组 NoOrderArray 中指定索引的元素。 <br>
 80    * 
 81    * @param index int - 索引值。
 82    * 
 83    * @return Object - 对应的元素。
 84    */
 85   public Object get(int index)
 86   {
 87     if (index >= size || index < 0)
 88       throw new IndexOutOfBoundsException("Index out of bounds.");
 89 
 90     return values[index];
 91   }
 92 
 93   /**
 94    * 判断当前 NoOrderArray 数组是否为空。 <br>
 95    * 
 96    * @return boolean - 如果为空返回 <code>true</code>.
 97    */
 98   public boolean isEmpty()
 99   {
100     return (size == 0);
101   }
102 
103   /**
104    * 移除 NoOrderArray 数组中指定位置的元素。 <br>
105    * 
106    * @param index int - 索引值。
107    * 
108    * @return Object - 被移除的元素。
109    */
110   public Object remove(int index)
111   {
112     if (index >= size || index < 0)
113       throw new IndexOutOfBoundsException("Index out of bounds.");
114 
115     Object value = values[index];
116 
117     if (index != size - 1)
118     {
119       // 将数组最后一个值补充到被移除的位置。
120       values[index] = values[size - 1];
121     }
122     values[size - 1] = null; // 防止该位置永久持有对象的引用
123     size --;
124 
125     return value;
126   }
127 
128   /**
129    * 判断指定的数据是否在 NoOrderArray 数组中。 <br>
130    * 
131    * @param value Object - 需要判断的数据。
132    * 
133    * @return boolean - 如果包含返回 <code>true</code>.
134    */
135   public boolean contains(Object value)
136   {
137     if (value == null)
138     {
139       for (int i = 0; i < size; i ++)
140         if (values[i] == null)
141           return true;
142     }
143     else
144     {
145       for (int i = 0; i < size; i ++)
146         if (value.equals(values[i]))
147           return true;
148     }
149 
150     return false;
151   }
152 
153   /**
154    * 返回当前数组的大小。 <br>
155    * 
156    * @return int - 当前数组的大小。
157    */
158   public int size()
159   {
160     return size;
161   }
162 
163   /*
164    * (non-Javadoc)
165    * 
166    * @see java.lang.Object#toString()
167    */
168   public String toString()
169   {
170     StringBuffer buffer = new StringBuffer();
171 
172     buffer.append('[');
173 
174     for (int index = 0; index < size; index ++)
175     {
176       Object value = values[index];
177 
178       if (index > 0)
179         buffer.append(',');
180 
181       buffer.append(value);
182     }
183 
184     buffer.append(']');
185 
186     return buffer.toString();
187   }
188 
189   /**
190    * @param args
191    */
192   public static void main(String[] args)
193   {
194     // TODO 自动生成方法存根
195   }
196 }


posted on 2007-08-27 17:18 Long 阅读(2927) 评论(9)  编辑  收藏 所属分类: Java

评论

# re: 快速随机访问和可删除的数组 2007-08-28 00:21 姜利阳
不错!  回复  更多评论
  

# re: 快速随机访问和可删除的数组 2007-08-28 10:22 dennis
这个东西不仅仅是无序这样的缺点,在大规模数据remove的时候将占据大量无效的内存,因为remove方法仅仅将value[size-1]赋给value[index],然后size--,可没有将value[size-1]设置为null,这个值尽管已经不用且不可访问,但是将一直占据在内存里直到整个数组被弃用。修改下remove方法:
public Object remove(int index) {
if (index >= size || index < 0)
throw new IndexOutOfBoundsException("Index out of bounds.");

Object value = values[index];

if (index != size - 1) {
// 将数组最后一个值补充到被移除的位置。
values[index] = values[size - 1];
values[size - 1] = null; //设置为null
}

size--;

return value;
}  回复  更多评论
  

# re: 快速随机访问和可删除的数组 2007-08-28 10:22 dennis
况且,我认为这个需求一般用哈希表更好点。  回复  更多评论
  

# re: 快速随机访问和可删除的数组 2007-08-28 10:35 Long
@dennis
楼上朋友,
我曾经考虑过将values[size - 1] = null;但是没有考虑周全。当时只考虑到values[size - 1] 的值被先前Remove掉的那个元素位置引用,所以没有必要设置为null。忽视了这个值可能再次被Remove掉而数组仍然持有引用。
谢谢提醒。

另外,哈希表的确是一个好东东,不过对于一个频繁使用的、数据元素超多、哈希值分布不均匀的应用时,太浪费内存空间了。

问题已修正。
  回复  更多评论
  

# re: 快速随机访问和可删除的数组 2007-08-30 12:46 JAVA面试题
同意  回复  更多评论
  

# re: 快速随机访问和可删除的数组 2009-03-16 12:55 sun java 工程师
不是吧,你的这些操作,ArrayList接口已经帮你全都弄好了。为什么自己再弄一个。

你说的对,ArrayList插入或删除一次数据就会产生一次大量数组内容Copy的操作。确实是这样。

可是单独增加一个值,并没有进行那么复杂的操作,具体请看ArrayList.add(E e)这个方法。

你的上面的代码的实现,在ArrayList中已经都有了。好好研究ArrayList吧。
另外说一点你上面的代码 remove(int index),你的这个方法已经实现了,但是改变了数组的顺序,凭什么把最后一个数据插入到index这个位置。理论上都是顺移顺序的。  回复  更多评论
  

# re: 快速随机访问和可删除的数组 2009-03-16 13:00 xx
@sun java 工程师
注意是快速随机访问和快速可删除。
ArrayList无法做到快速可删除。  回复  更多评论
  

# re: 快速随机访问和可删除的数组 2009-03-16 13:06 sun java 工程师
@Long
if (index != size - 1) { //如果相等怎么办???
// 将数组最后一个值补充到被移除的位置。
values[index] = values[size - 1];
values[size - 1] = null; //设置为null
}
size--;
可否改成一下代码
if (index != size - 1) {
// 将数组最后一个值补充到被移除的位置。
values[index] = values[size - 1];
}
values[size - 1] = null; //设置为null
size--;  回复  更多评论
  

# re: 快速随机访问和可删除的数组 2009-03-16 13:14 sun java 工程师
@xx
O(∩_∩)O哈哈~,看来都在看这边文章,如果不考虑顺序的话,按照上面的思路下来,本人建议继承ArrayList再写一个方法就OK了
如:
public class MyList<E> extends ArrayList<E>{
public Ojbect removeValue(int index){
if (index >= size || index < 0)
throw new IndexOutOfBoundsException("Index out of bounds.");
Object value = values[index];
if (index != size - 1) {
// 将数组最后一个值补充到被移除的位置。
values[index] = values[size - 1];
}
values[size - 1] = null; //设置为null
size--;
return value
}
}  回复  更多评论
  

# re: 快速随机访问和可删除的数组 2009-03-16 13:19 Long
@sun java 工程师
老兄说的是,
代码已修正。

呵呵,写这个类的时候没有继承自ArrayList的主要原因是为了保持它的接口的简单性,因为ArrayList的接口中有很多与Array的顺序/序号操作的相关,比如add(int,object)等等。  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: