查找、插入及删除时间为O(1)的方法研究  

Study of operation of insertion, search and deletion in O(1) time

作　　者：宫团基[1] 夏克俭[1] 

机构地区：[1]北京科技大学信息工程学院,北京100083

出　　处：《计算机工程与设计》2010年第9期2097-2100,共4页Computer Engineering and Design

摘　　要：提出一种查找、插入及删除对象时间为O(1)的方法,以双向链表存储数据对象,通过地址指针方式获取对象。即客户端与服务器进行数据的交互时,传输中包含对象在服务器的地址指针值,服务器根据地址指针值,直接获取对象信息的方式。同时提出了计算指针值的校验和的算法,解决验证地址的有效性问题和安全问题,及提出了细粒度锁对象方式解决并发访问的问题。A novel method of operation of insertion, search and deletion in O （1） time , which employs double-list to contain objects and obtains object by converting address pointer to object pointer, is proposed. In the course of interactive between client and server, data frame consists of the address value which server allocates for object. Server receives data frame and extracts address value, computer checksum and convert to object pointer. In order to assure the address which is a valid address and the object that the address point to still exists in server, a checksum algorithm is adopted. In addition, thin-granule lock mechanism involved concurrency access is employed.

关 键 词：地址指针 数据帧传输协议(SCMP) 映射 双向链表 校验和 

分 类 号：TP302.7[自动化与计算机技术—计算机系统结构]