Question

Android开发中ArrayMap与HashMap有哪些不同

Answer 1

1、存储方式不同

HashMap内部有一个HashMapEntry<K, V>[]对象，每一个键值对都存储在这个对象里，当使用put方法添加键值对时，就会new一个HashMapEntry对象，具体实现如下：

[java] view plaincopy
@Override public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}

int hash = secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
//先查找有没有对应的key值，如果有，就改写value，并返回改写前的value值：oldValue
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}

// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
//扩容，双倍
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
}
//创建对象存储键值对
void addNewEntry(K key, V value, int hash, int index) {
table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}

ArrayMap的存储中没有Entry这个东西，他是由两个数组来维护的
[java] view plaincopy
int[] mHashes;
Object[] mArray;

mHashes数组中保存的是每一项的HashCode值，mArray中就是键值对，每两个元素代表一个键值对，前面保存key，后面的保存value，我们看看下面代码的结果：
[java] view plaincopy
arraymap = new HashMap<String, String>();
a.put("a", "a_value");
a.put("b", "b_value");
执行上面代码后，arraymap中的存储是这样的

是不是能清楚地看到ArrayMap的存储了，这种存储在put代码中如下：

[java] view plaincopy
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;

2、添加数据时扩容时的处理不一样

先来看看HashMap

[java] view plaincopy
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}

doubleCapacity进行双倍扩容，它的代码中有这么一句话
[java] view plaincopy
HashMapEntry<K, V>[] newTable = makeTable(newCapacity);

最终，这个newTable将作为扩容后的新对象返回，那么makeTable做了什么呢，如下：
[java] view plaincopy
private HashMapEntry<K, V>[] makeTable(int newCapacity) {
@SuppressWarnings("unchecked") HashMapEntry<K, V>[] newTable
= (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity];
table = newTable;
threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity
return newTable;
}

我们清楚地看到，这里进行了new操作，重新创建对象，开销很大。
那么ArrayMap呢，看看：

[java] view plaincopy
//如果容量不够
ize >= mHashes.length) {
final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
: (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);

final int[] ohashes = mHashes;
final Object[] oarray = mArray;
//分配数组
allocArrays(n);

if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
//特别注意这，是copy，而不是new，效率提升
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
//释放无用空间，收缩数组
freeArrays(ohashes, oarray, mSize);
}

ArrayMap用的是copy数据，所以效率相对要高。

3、ArrayMap提供了数组收缩的功能，在clear或remove后，会重新收缩数组，是否空间

4、ArrayMap采用二分法查找；

以上就是android开发中，HashMap与ArrayMap的区别，大家在涉及到内存方面的实现，可根据实际情况选择这两种不同的方式。

Answer 2

常用的集合类有一下几种：
List结构的集合类：ArrayList类，LinkedList类，Vector类，Stack类
Map结构的集合类：HashMap类，Hashtable类
Set结构的集合类：HashSet类，TreeSet类
Queue结构的集合：Queue接口

HashMap和Hashtable的区别：
HashMap和Hashtable都是java的集合类，都可以用来存放java对象，这是他们的相同点
以下是他们的区别：
1.历史原因：
Hashtable是基于陈旧的Dictionary类的，HashMap是java 1.2引进的Map接口的一个现实。
2.同步性：
Hashtable是同步的，这个类中的一些方法保证了Hashtable中的对象是线程安全的，而HashMap则是异步的，因此HashMap中的对象并不是线程安全的，因为同步的要求会影响执行的效率，所以如果你不需要线程安全的结合那么使用HashMap是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销，从而提高效率，我们一般所编写的程序都是异步的，但如果是服务器端的代码除外。
3.值：
HashMap可以让你将空值作为一个表的条目的key或value
Hashtable是不能放入空值（null）的