本节书摘来自华章出版社《深入理解Android》一书中的第3章，第3.4节，作者孟德国 王耀龙 周金利 黎欢，更多章节内容可以访问云栖社区“华章计算机”公众号查看
3.4 内存管理与容器
WTF作为一个基础库存在，它提供的内存管理手段与STL类似，主要是为容器和应用类提供了便捷高效的内存分配接口（当然一些内部使用的内存对齐接口也是必不可少的）。其中，OSAllocator和PageAllocation类只应用于JavaScriptCore（Safari使用的JS引擎）中，这里不做分析。本节重点分析FastAllocator，这里的FastAllocator是指封装FastMalloc得到的WTF_MAKE_FAST_ALLOCATED、FastNew/FastDelete以及FastNewArray/FastDeleteArray。
3.4.1 FastAllocator的实现及使用
众所周知，STL中的Allocator在libc提供的malloc之上实现了一个memory pool，以此来实现高效的内存分配和回收（可参考《STL源码剖析》第2章，当然最新STL的allocator的实现跟书中的描述已有较大差别），而WTF则走了另一条路——实现一个高效的malloc。
【→Wtf/FastMalloc.cpp : 3823行】
template<bool crashOnFailure>
ALWAYS_INLINE void *malloc(size_t size);
WTF中使用条件编译宏FORCE_SYSTEM_MALLOC来控制是否使用libc提供的malloc。在FORCE_SYSTEM_MALLOC为0时，上述自定义的malloc在fastMalloc/tryFastmalloc中被调用。该malloc本质上就是TCMalloc的再封装。TCMalloc性能远优于libc malloc，它为每个线程分配thread-local cache。对于尺寸≤32KB的内存分配请求直接从thread-local cache中分配，并且按8的整数倍尺寸分配。而对于>32KB的内存分配请求则从堆中分配，并按照4KB的整数倍分配。此外，TCMalloc还提供了垃圾回收策略。
关于TCMalloc的实现可以参考：http://goog-perftools.sourceforge.net/doc/tcmalloc.html。
但Android 4.2版的WebKit没有使用TCMalloc实现的malloc，也就是说fastMalloc/tryFastmalloc最终使用的还是bionic提供的malloc函数。fastMalloc在Android平台没有实现全功能porting。
【→FastAllocBase.h】
#define WTF_MAKE_FAST_ALLOCATED \
public: \
void* operator new(size_t, void* p) { return p; } \
void* operator new[](size_t, void* p) { return p; } \
\
void* operator new(size_t size) \
{ \
void* p = ::WTF::fastMalloc(size); \
::WTF::fastMallocMatchValidateMalloc(p, ::WTF::Internal::AllocTypeClassNew); \
return p; \
} \
\
void operator delete(void* p) \
{ \
::WTF::fastMallocMatchValidateFree(p, ::WTF::Internal::AllocTypeClassNew); \
::WTF::fastFree(p); \
} \
\
void* operator new[](size_t size) \
{ \
void* p = ::WTF::fastMalloc(size); \
::WTF::fastMallocMatchValidateMalloc(p, ::WTF::Internal::AllocTypeClassNewArray); \
return p; \
} \
\
void operator delete[](void* p) \
{ \
::WTF::fastMallocMatchValidateFree(p, ::WTF::Internal::AllocTypeClassNewArray); \
::WTF::fastFree(p); \
} \
private: \
typedef int ThisIsHereToForceASemicolonAfterThisMacro
在WebKit代码类的声明中，经常看到上述宏。该宏为类定义了标准的operator new和operator delete以及placement new。
::WTF::fastMallocMatchValidateFree(p, ::WTF::Internal::AllocTypeClassNewArray);
在Android 4.2平台上是一个空函数，也就是这里的operator new 直接调用fastMalloc来完成内存的分配，前面分析过fastMalloc内部其实就是直接调用malloc。由此我们也可以得出一个结论，malloc返回的内存指针在对齐性等方面满足operator new的要求。其实STL提供的部分Allocator内部也直接使用malloc分配内存。由于这里定制了类的operator new 和operator delete，因此如果在这个宏中添加log或者统计算法，可以分析声明了WTF_MAKE_FAST_ALLOCATED的类的对象的创建和销毁情况，进而辅助分析内存泄露或其他问题。
3.4.2 容器类概述
WTF提供了为数众多的容器类，比如BlockStack、 ByteArray、 FixedArray、 Deque、 Vector、 HashTable等。本节重点分析Vector和HashTable的实现及使用，以此为基础，其余几种容器的实现及使用，读者可自行分析。
- Vector的实现及使用
WTF中的Vector与STL中的Vector的行为基本一致，对外呈现的也是动态数组的行为。
【→Vector.h】
template<typename T, size_t inlineCapacity = 0>
class Vector {
WTF_MAKE_FAST_ALLOCATED;
private:
typedef VectorBuffer<T, inlineCapacity> Buffer;
typedef VectorTypeOperations<T> TypeOperations;
public:
typedef T ValueType；
//关键点(1)
typedef T* iterator;
//关键点(2)
typedef const T* const_iterator；
explicit Vector(size_t size) : m_size(size) , m_buffer(size)
{
if (begin())
TypeOperations::initialize(begin(), end());
}
~Vector() { if (m_size) shrink(0); }
//关键点(3)
size_t size() const { return m_size; }
//关键点(4)
size_t capacity() const { return m_buffer.capacity();}
//关键点(5)
T& at(size_t i) ;
//关键点(6)
T& operator[](size_t i) { return at(i); }
//关键点(7)
iterator begin() { return data(); }
//关键点(8)
iterator end() { return begin() + m_size; }
////关键点(9)
template<typename U> size_t find(const U&) const;
void shrink(size_t size);
void grow(size_t size);
void resize(size_t size);
void reserveCapacity(size_t newCapacity);
void reserveInitialCapacity(size_t initialCapacity);
void shrinkCapacity(size_t newCapacity);
void remove(size_t position);
private:
void expandCapacity(size_t newMinCapacity);
const T* expandCapacity(size_t newMinCapacity, const T*);
bool tryExpandCapacity(size_t newMinCapacity);
const T* tryExpandCapacity(size_t newMinCapacity, const T*);
template<typename U> U* expandCapacity(size_t newMinCapacity, U*);
size_t m_size;
Buffer m_buffer;
};
上面代码截取的是Vector中重要的实现函数，下面分析Vector的几个重要成员。
关键点（1）（2）：由于Vector采用连续存储结构，因此这里的iterator直接使用了原生指针。
关键点（3）（4）：函数size()返回的是Vector中已存储的元素数目，而capacity()返回的是Vector所使用的Buffer的容量，这个capacity随元素增删的变化，也就是 Vector内存管理的核心内容。
关键点（5）（6）：为Vector提供了数组访问的行为，这也是Vector动态数组行为的关键点。
关键点（7）（8）：提供了获取iterator的接口，与使用STL容器的iterator一样，Vector的iterator的begin与end是会随着对Vector的修改而变化的，比如通过iterator完成的一次遍历操作中，若伴随对Vector元素的插入或删除操作，那么每一次操作完毕都要重新获取begin或end。
关键点（9）：提供的find操作是一个O(N)的顺序遍历查找操作，如果用Vector来存储大量数据，而用它提供的find操作来查找元素，并不高效。
介绍Vector的主要行为后，再来看一下Vector的存储结构，本节不再仔细列举VectorBuffer和VectorTypesOperations的实现，只在宏观上说明这两个类的原理。
Vector用VectorBuffer作为内部存储数据的容器，而VectorBuffer的实现是通过fastMalloc来分配内存，用placement new来初始化对象（前面讲过malloc分配的内存满足operator new分配内存的要求），这样将Vector中对象的存储空间分配与对象初始化分开。
Vector中元素的初始化、复制、移动等操作由VectorTypesOperations来封装，其中成员函数的行为因数据类型的不同而不同，具体行为由VectorTraits封装的编译时类型计算信息控制。
当Vector因append函数或insert函数调用而引起内存空间不足时，间接调用reserveCapacity()来重新分配内存，并释放原来使用的内存空间。当Vector通过remove函数移除掉一些元素时，只是简单析构原来的对象。整个内存原理的示意图为图3-1。
图3-1中，begin指针代表begin()返回的iterator，end指针代表end()返回的iteraror。size()表示的范围为Vector中含有元素的部分，capacity表示已经分配的空间。扩展空间部分表示在insert函数或append函数等操作引起额外空间分配时，要重新分配的空间。
- HashTable的实现及使用
HashMap和HashSet的实现代码非常简单，几乎每一个函数都只有几行代码，原因就在于支撑它们的幕后高手是HashTable。HashTable作为HhashMap和HashSet的m_impl字段帮它们打理好了一切。
【→HashTable.h】
template<typename Key, typename Value, typename Extractor, typename
HashFunctions, typename Traits, typename KeyTraits>
class HashTable {
public:
typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
typedef Traits ValueTraits;
typedef Key KeyType;
typedef Value ValueType;
iterator begin() { return makeIterator(m_table); }
iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
int size() const { return m_keyCount; }
int capacity() const { return m_tableSize; }
pair<iterator, bool> add(const ValueType& value) { return add<KeyType,
ValueType, IdentityTranslatorType>(Extractor::extract(value), value); }
iterator find(const KeyType& key) { return find<KeyType,
IdentityTranslatorType>(key); }
bool contains(const KeyType& key) const { return contains<KeyType, IdentityTranslatorType>(key); }
void remove(const KeyType&);
void remove(iterator);
void clear();
private:
static ValueType* allocateTable(int size);
static void deallocateTable(ValueType* table, int size);
void expand();
void shrink() { rehash(m_tableSize / 2); }
static const int m_minTableSize = 64;
static const int m_maxLoad = 2;
static const int m_minLoad = 6;
ValueType* m_table;
int m_tableSize;
int m_tableSizeMask;
int m_keyCount;
int m_deletedCount;
#if CHECK_HASHTABLE_ITERATORS
public:
// All access to m_iterators should be guarded with m_mutex.
mutable const_iterator* m_iterators;
mutable Mutex m_mutex;
#endif
};
一切的故事都从HashTable的创建说起：
通过HashTable的构造函数可知，初创建时HashTable的内容是空的，多数字段都是简单地初始化为0。
调用HashTable的add函数添加元素时，add内部通过expand函数来扩张内存空间，expand会调用fastMalloc来分配空间，分配空间的大小为：m_minTableSize = 64（此后再次需要分配空间时，分配的空间为原来空间的大小乘2），然后调用rehash函数，会在其中设置m_tableSizeMask = newTableSize–1，此处的m_tableSizeMask用在了寻址过程中，也就是lookup函数的实现中。
HashTable内部有两个lookup函数，一个是有一个参数的普通成员函数：
ValueType * lookup(const Key& key) {return lookupIdentifyTranslatorType>(key); } //实现(1)
它内部调用了lookup的另一种模板实现：
template ValueType* lookup(const T&);//实现(2)
实现（1）更频繁地被类外使用，比如在HashMap的get函数就是用了实现（1）。在该应用场景下实现（2）的第二个模板参数为IdentifyTranslatorType，而HashTable的HashFunctions参数为DefaultHash::Hash，这里的KeyArg也就是HashMap的KeyArg参数。因此在lookup函数内部HashTranslator::hash(key)最终使用的是HashFunctions.h文件中定义的DefaultHash::Hash，也就是IntHash::Hash，其作用是将输入的各种宽度的key值折算成unsigned int 类型的散列值，参与寻址运算。
下面截取lookup函数的关键点：
unsigned h = HashTranslator::hash(key);
int i = h & sizeMask;
这里的i作为table的index来存放数据，这也就是真正的寻址算法。如果这一次没有在HashMap上找到合适的位置，那么接下来的动作是调用新的hash算法：
if (k == 0){
k = 1 | doubleHash(h);
i = (i + k) & sizeMask;
}
也就是说HashTable本质上用线性结构存储，而解决hash冲突的方法是二次hash。
图3-2中，begin和end表示HashTable使用线性存储空间的起始和结束地址，capacity为存储空间的大小。在存储空间不足时，存储空间尺寸扩展为原来的两倍。
接下来分析HashTable的iterator的实现。HashTable的iterator是在调用begin或end时创建的，最本质的iterator对象是const_iterator, 而const_iterator内部也只是维持了一个指向value_type的指针而已，之所以如此是因为HashTable是线性存储的，进而iterator的自增或者自减操作也是简单的指针自增和自减操作，所以WTF的HashTable的iterator要比STL的HashMap的iterator实现简单（STL的HashMap使用数组加链表存储结构，用链表来解决hash冲突）。
