PHP的array是真正的数组吗 我看PHP语法中,数组的下标除了是数字外同样可以有类似哈希的key。那么PHP中的数组对象是不是不是真正的数据结构中的ARRAY。同时,但我设定了KEY时是不是就是可以当作HASH去使用,读取的时间复杂度是不是O(1)的? 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 在PHP中, 数组是用一种HASH结构(HashTable)来实现的, PHP使用了一些机制, 使得可以在O(1)的时间复杂度下实现数组的增删, 并同时支持线性遍历和随机访问. PHP的数组Array是列表List,散列表/关联数组/字典Hashtable的聚合体。既然array具有hashtable的性质 那么通过key值读取,他的时间复杂度当然是O(1)的! 在PHP内部Array通过一个hashtable来实现,其中使用链接法解决hash冲突的问题,这样最坏情况下,查找Array元素的复杂度为O(N),最好则为1. 如果不是链表,那你如何解释一下函数reset、prev、next、end又,一般说 hash 表的时间复杂度是O(1)这是理论上的,它假定键足够长但实际应用时,键冲突是必然存在的。 hash 表在出现键冲突时采用顺序表来弥补 贴个网址: http://www.codinglabs.org/html/hash-collisions-attack-on-php.html php键的冲突 解决冲突用的是单链表 那是链表的话,是不是我向一个数组中插入100W条记录。哪怕指定了KEY。但是查找起来还是O(n)的? 详解PHP中Array结构HashTablehttp://www.cnblogs.com/wgw8299/articles/2275572.html插入A,B,C三个值之后的内存中状态即为:HashTable.arBucket[1] = C;HashTable.pListHead = AHashTable.pListTail =CHashTable.pInternalPointer = AA.pNext=nullA.pLast = CA.pListNext = BA.pListLast = null B.pNext = nullB.pLast = nullB.pListLast = AB.pListNext = CC.pNext = AC.pLast = nullC.pListNext = nullC.pListLast = B 查找某key的元素值(value):如果我们要访问A元素,则提供A的key:key_a,得到对应的hash值为1然后找HastTable.arBucket[1]。这时HastTable.arBucket[1]其实为C不是A,但由于C的key不等于A的key,因此,要沿着pNext的指针找下去,直到NULL,而此时C.pNext就是A,即找到了key_a对应的值A。总之由key查找一个元素时,首先要hash,然后顺着hash后的索引位置的pNext指针一直找下去,直到NULL,如果遇到了和要查找的key相同的值,则找到,否则找不到。 哈稀表+链表参见php开发组成员laruence的文章http://www.laruence.com/2009/08/23/1065.html hash是O(1),除非你刻意制造的下标,导致hash冲突前段时间不是java ruby php啥的都中招了吗。。hash算法开源的要说链表,还是双向的prev next hash攻击那个?http://www.laruence.com/2011/12/30/2435.html Hash只能保证桶内有序, 如果坚持用哈希表而不用红黑树的话, 需要维护一个按Key有序的Hash node链表.这样就可以同时满足:1, 哈希表按key的O(1)的随机查询2, 按key有序的遍历Hash node链表.3, 支持链表按key的归并(array_uniq), 按key的排序, 按val的排序, 等等.为什么要这样做?Hash支持O(1)按key查找,而因为array提供了很多额外的特性, 比如按key排序,按val排序,操作hash表很难满足这些特性, 所以需要额外的存储容器来实现灵活的改变访问顺序这个功能.在C语言里, 哈希表的Node和链表里的Node是同一个内存, Node有链表的prev,next,也有哈希链表的hash_prev,hash_next。Php目前使用链表维护索引, 在很多操作中都要执行链表快排, 链表不支持随机访问, 所以快排性能有所下降,但是它的内存消耗又是比较低的, 很难说用顺序内存取代链表. 而如果用红黑树等平衡二叉树做索引, 又会面临的问题就是经常重新建树, 因为只要用户的排序要求变了, 就得重新建树, 而且支持array_asort的时候会显得更加恶心. 这个数据结构和memached里的hashtable+lru list实现是基本一致的,只不过memached又结合的slab。 有谁能给我个页面回退的例子 请问,在做留言本的时候,怎么样过滤字符? 数据库查询存为数组问题。 关于Thinkphp中SQL语句 PHP补基础 彭和平垃圾回收机制 在Linux下升级PHP4要注意什么? 服务器重起,只要客户端页面不关闭,等服务器起来后客户端居然还能继续使用,为什么 能不能用程序实现数据到入!!! 我下載時的文件路徑是怎樣寫的? html中php值传递到JS 关于PHP5扩展的问题
既然array具有hashtable的性质 那么通过key值读取,他的时间复杂度当然是O(1)的!
reset、prev、next、end又,一般说 hash 表的时间复杂度是O(1)
这是理论上的,它假定键足够长
但实际应用时,键冲突是必然存在的。 hash 表在出现键冲突时采用顺序表来弥补
http://www.cnblogs.com/wgw8299/articles/2275572.html插入A,B,C三个值之后的内存中状态即为:
HashTable.arBucket[1] = C;
HashTable.pListHead = A
HashTable.pListTail =C
HashTable.pInternalPointer = A
A.pNext=null
A.pLast = C
A.pListNext = B
A.pListLast = null
B.pNext = null
B.pLast = null
B.pListLast = A
B.pListNext = C
C.pNext = A
C.pLast = null
C.pListNext = null
C.pListLast = B
查找某key的元素值(value):
如果我们要访问A元素,则提供A的key:key_a,得到对应的hash值为1
然后找HastTable.arBucket[1]。这时HastTable.arBucket[1]其实为C不是A,但由于C的key不等于A的key,因此,要沿着pNext的指针找下去,直到NULL,而此时C.pNext就是A,即找到了key_a对应的值A。
总之由key查找一个元素时,首先要hash,然后顺着hash后的索引位置的pNext指针一直找下去,直到NULL,如果遇到了和要查找的key相同的值,则找到,否则找不到。
参见php开发组成员laruence的文章
http://www.laruence.com/2009/08/23/1065.html
要说链表,还是双向的prev next
http://www.laruence.com/2011/12/30/2435.html
2, 按key有序的遍历Hash node链表.
3, 支持链表按key的归并(array_uniq), 按key的排序, 按val的排序, 等等.为什么要这样做?Hash支持O(1)按key查找,而因为array提供了很多额外的特性, 比如按key排序,按val排序,操作hash表很难满足这些特性, 所以需要额外的存储容器来实现灵活的改变访问顺序这个功能.在C语言里, 哈希表的Node和链表里的Node是同一个内存, Node有链表的prev,next,也有哈希链表的hash_prev,hash_next。
Php目前使用链表维护索引, 在很多操作中都要执行链表快排, 链表不支持随机访问, 所以快排性能有所下降,但是它的内存消耗又是比较低的, 很难说用顺序内存取代链表. 而如果用红黑树等平衡二叉树做索引, 又会面临的问题就是经常重新建树, 因为只要用户的排序要求变了, 就得重新建树, 而且支持array_asort的时候会显得更加恶心.
这个数据结构和memached里的hashtable+lru list实现是基本一致的,只不过memached又结合的slab。