php中如何找出一个哈希数组中的某个元素的前后项

Question

这个标题看起来比较绕口，我直接上代码吧，比如有下面这样一种形式组织的数组

$a = array(
    'key12'    =>    12323,
    'key32'    =>    4345,
    'key13'    =>    323423,
    'key43'    =>    32423,
    'key25'    =>    33423
);

对于一个未知的数组，我知道了其中任意一个已经存在的元素的键值，比如就是key13吧，那我如何知道key13的前后分别是哪两个键呢？比如在这个例子中，我如何才能知道$a和key13，找出key32和key43呢？

这种哈希数组没有顺序的数值键值，因此不能对键值+1或者-1，来获取前驱和后继，不知道各位有什么好办法？

Answer 1

可以参考下php - Search array keys and return the index of matched key - Stack Overflow，思路是找出key所在的索引，然后根据索引再减1或加1取得前后项：http://stackoverflow.com/questions/37...

我写了段测试代码：

<?php
$a = array(
    'key12'    =>    12323,
    'key32'    =>    4345,
    'key13'    =>    323423,
    'key43'    =>    32423,
    'key25'    =>    33423
);
print_r($a);
echo "<br>";

$key = 'key13';

// 寻找key的索引号
$keys = array_keys($a);
$key_index = array_search($key, $keys);
echo "index of $key is $key_index<br/>";

// 将key索引号减1或加1取得前项和后项索引（注意要判断是否越界）
if ($key_index == 0) echo 'no pre key<br/>';
else echo 'pre key is ' . $keys[$key_index - 1] . '<br/>';

if ($key_index < count($keys)) echo 'next key is ' . $keys[$key_index + 1] . '<br/>';
else echo 'no next key<br/>';
?>

Answer 2

null的说的对（已经点了赞了），在php function层面（Zend API层面我不知道），没有办法绕过数组遍历，代码大概像这样(随手写的伪代码，不能执行的，下同)：

<?php
$a = array(....);
$ele = current($a);
while (FALSE !== $ele)
{
    if (你在找的VALUE（不是 KEY）!==$ele)
    {
        $ele = next($a);
    }
    else
    {
        分别用next(), prev()取出你要的值
        break;
    }
}

如果你要找的值不是数组倒数第一/二个，不会遍历整个数组。

但这种写法对你的代码能力要求较高，代码量大一些，看起来不直观，你要注意：
1. current()取出来的元素value值恰好是false的时候容易出错，须使用===比较操作符
2. while循环第一轮和最后一轮要特殊处理，因为你要找的值有可能恰好在数组的头尾上，没有prev或者next
3. current,next,prev取出元素值的同时，也移动了数组内部指针，这几个函数比较小众，接手维护的人可能看不懂

采用何志强同学的方案，代码就简洁多了：

<?php
$keys = array_key($a);
$mid_number_index = array_search(你在找的KEY（不是VALUE）, $keys);

if (0 < $mid_number_index)
{
    $prev_key = $mid_number_index-1;
    $prev_value = $a[$prev_key];
}

if (sizeof($a) > $mid_number_index)
{
    $next_key = $mid_number_index+1;
    $next_value = $a[$next_key];
}

很显然，这个方案有两个性能稍差的地方：
1.array_keys()一定要遍历全部数组元素
2.array_search()搜索时还要遍历（但中途找到就break了）

如果你的数组不是很大，推荐用何志强同学的方案写代码。

Answer 3

php 的array 是hash+双向链表的结构实现的. 参考php 源码: Zend/zend_hash.h

typedef struct _hashtable {
	uint nTableSize;
	uint nTableMask;
	uint nNumOfElements;
	ulong nNextFreeElement;
	Bucket *pInternalPointer;	/* Used for element traversal */
	Bucket *pListHead;
	Bucket *pListTail;
	Bucket **arBuckets;
	dtor_func_t pDestructor;
	zend_bool persistent;
	unsigned char nApplyCount;
	zend_bool bApplyProtection;
#if ZEND_DEBUG
	int inconsistent;
#endif
} HashTable;

其中pInternalPointer 就是数组的内部指针. 如果内部指针指向位置ok,可以获取链表的前后项目指针. 但目前没有发现 php 提供根据 key 来设置 array 的 internal pointer 的外部函数. 所以线性遍历不可避免了.

看到有一种相对简洁的方法:

$a = array(
    'key12'    =>    12323,
    'key32'    =>    4345,
    'key13'    =>    323423,
    'key43'    =>    32423,
    'key25'    =>    33423
);
while(key($a) !== 'key13') next($a);
$prev_val = prev($array);# 前一项的value
$prev_key = key($array);# 前一项的key

获取后一项用 next 函数, 方法类似.

参考: http://stackoverflow.com/questions/47...

Answer 4

遍历数组再通过prev/next这些函数操作， 或者提取keys组成新数组,然后通过value(原先的key值)取数字下标,再对应key

大体除了这些好像没太好的办法

Answer 5

楼上提到的方法都需要把整个数组过一遍，效率比较低，限于语言层面的原因，只使用php语言本身也只能达到这个程度。

但是正如 @liruqi 同学的答案，PHP实际上是使用了HASH+双向链表的方式来实现的，所以如果给PHP写一个C扩展的话，可以用O(1)的时间来获得你要的答案。