数据结构：散列表&XArray

散列表

散列表（Hash Table，也叫哈希表），是根据关键码值（Key，Value）直接进行访问的数据结构

• 通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度
• 这个映射函数叫做哈希函数（散列函数），存放记录的数组叫做散列表

散列表的基本思想就是“链表的数组”：

运用流程如下：

• 利用 Hash 算法来来把一个不同长度的特征值转化成杂乱的128位的编码
• 将目标编码转变为数组下标
• 在散列表中索引对应的链表，然后插链

相比于正常的链表，散列表在插链之前先对链表的各个节点进行了“分组”（依赖哈希函数的无规律分组），在之后的查找/脱链过程中，程序只需要遍历对应的链表，而不是从头开始把所有的节点都遍历一遍

将目标编码转变为数组下标的方法就是散列法，常见的散列法如下：

• 除法散列法：
  • 对目标编码进行取模
  • index = value % 16
• 平方散列法：
  • 乘法的运算要比除法来得省时，所以把除法换成乘法和一个位移操作
  • index = (value * value) >> 28（value的类型为int，乘法的结果不会超过32位）
• 斐波那契（Fibonacci）散列法：
  • 找出一个理想的乘数，而不是拿 value 本身当作乘数
  • index = (value * 2654435769) >> 28

散列表的优缺点如下：

• 优点：
  • 不论散列表中有多少数据，查找/插入/删除只需要接近常量的时间即 0(1) 的时间级（实际上只需要几条机器指令）
  • 散列表的编程实现也相对容易
• 缺点：
  • 散列表是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重
  • 程序员必须要清楚表中将要存储多少数据，或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程

XArray

XArray 是一种抽象的数据类型，其行为类似于一个非常大的指针数组，它满足了与散列或常规可调整大小的数组相同的许多需求

• 与散列表 (Hash Table) 相比：它允许您以高效缓存的方式明智地转到下一个或上一个条目
• 与可调整大小的阵列 (Array Data Structure，多维数组) 相比：无需为了扩展阵列而复制数据或更改 MMU 映射
• 与双向链接列表相比：它具有更高的内存效率，可并行性和缓存友好性
• 它利用 RCU 来执行查找而无需锁定

XArray 其实是根据基数树 Radix Tree 修改而来的：保持基数树的数据结构不变，将结构更改为数组

先对比一下 XArray 和 Radix Tree 的创建函数：

• XArray：

static void *xas_create(struct xa_state *xas)
{
	struct xarray *xa = xas->xa;
	void *entry;
	void __rcu **slot;
	struct xa_node *node = xas->xa_node;
	int shift;
	unsigned int order = xas->xa_shift;

	if (xas_top(node)) { /* 获取Root节点 */
		entry = xa_head_locked(xa);
		xas->xa_node = NULL;
		shift = xas_expand(xas, entry); /* 实现XArray纵向的生长 */
		if (shift < 0)
			return NULL;
		entry = xa_head_locked(xa);
		slot = &xa->xa_head;
	} else if (xas_error(xas)) {
		return NULL;
	} else if (node) {
		unsigned int offset = xas->xa_offset;

		shift = node->shift;
		entry = xa_entry_locked(xa, node, offset);
		slot = &node->slots[offset];
	} else {
		shift = 0;
		entry = xa_head_locked(xa);
		slot = &xa->xa_head;
	}

	while (shift > order) {
		shift -= XA_CHUNK_SHIFT;
		if (!entry) {
			node = xas_alloc(xas, shift); /* 结点分配 */
			if (!node)
				break;
			if (xa_track_free(xa))
				node_mark_all(node, XA_FREE_MARK);
			rcu_assign_pointer(*slot, xa_mk_node(node));
		} else if (xa_is_node(entry)) { /* 判点是否为内部节点 */
			node = xa_to_node(entry);
		} else {
			break;
		}
		entry = xas_descend(xas, node); /* 节点查找 */
		slot = &node->slots[xas->xa_offset];
	}

	return entry;
}

• Radix Tree：

static int __radix_tree_create(struct radix_tree_root *root,
		unsigned long index, struct radix_tree_node **nodep,
		void __rcu ***slotp)
{
	struct radix_tree_node *node = NULL, *child;
	void __rcu **slot = (void __rcu **)&root->xa_head;
	unsigned long maxindex;
	unsigned int shift, offset = 0;
	unsigned long max = index;
	gfp_t gfp = root_gfp_mask(root);

	shift = radix_tree_load_root(root, &child, &maxindex); /* 获取Root节点 */

	/* Make sure the tree is high enough.  */
	if (max > maxindex) {
		int error = radix_tree_extend(root, gfp, max, shift); /* 实现radix tree纵向的生长 */
		if (error < 0)
			return error;
		shift = error;
		child = rcu_dereference_raw(root->xa_head);
	}

	while (shift > 0) {
		shift -= RADIX_TREE_MAP_SHIFT;
		if (child == NULL) {
			/* Have to add a child node.  */
			child = radix_tree_node_alloc(gfp, node, root, shift,
							offset, 0, 0); /* 结点分配 */
			if (!child)
				return -ENOMEM;
			rcu_assign_pointer(*slot, node_to_entry(child));
			if (node)
				node->count++;
		} else if (!radix_tree_is_internal_node(child)) /* 判点是否为内部节点 */
			break;

		/* Go a level down */
		node = entry_to_node(child);
		offset = radix_tree_descend(node, &child, index); /* 节点查找 */
		slot = &node->slots[offset];
	}

	if (nodep)
		*nodep = node;
	if (slotp)
		*slotp = slot;
	return 0;
}

两个函数之间，不管是函数名称还是执行流程，都有一些比较类似的地方，在条件符合时，两者可以互相替代

一些高版本的 kernel 开始使用 XArray 来替代原来的基数树：

• linux-2.6.34 的 address_space->i_pages 使用基数树

struct address_space {
	struct inode		*host;		/* owner: inode, block_device */
	struct radix_tree_root	page_tree;	/* radix tree of all pages */
	......

• linux-4.20.1 的 address_space->i_pages 使用 XArray

struct address_space {
	struct inode		*host;
	struct xarray		i_pages;
	......