Heim  >  Artikel  >  Backend-Entwicklung  >  php中如何找出一个哈希数组中的某个元素的前后项

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

WBOY
WBOYOriginal
2016-06-06 20:51:541061Durchsuche

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

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

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

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

回复内容:

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

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

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

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

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

我写了段测试代码:

";

$key = 'key13';

// 寻找key的索引号
$keys = array_keys($a);
$key_index = array_search($key, $keys);
echo "index of $key is $key_index
"; // 将key索引号减1或加1取得前项和后项索引(注意要判断是否越界) if ($key_index == 0) echo 'no pre key
'; else echo 'pre key is ' . $keys[$key_index - 1] . '
'; if ($key_index '; else echo 'no next key
'; ?>

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了)

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

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...

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

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

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

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

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn