python技术面试题(二十)
正文共：1744 字 5 图 预计阅读时间：5 分钟
每日分享
The struggle you're in today is developing the strength you need for tomorrow.
今天拼搏的是明天你需要的力量。
小闫语录：
没有无畏的奋斗，也没有无用的经历。现在所经历的都会成为将来你厚积薄发的蓄力，加油！
1.笔试题
1.1 哈希树
哈希树是专门优化查询效率的一种数据结构，这棵树查询效率极高，单论查询，要比二叉排序树快。
哈希树是通过质数分辨算法建立的，所以我们首先来看一下质数分辨算法。
质数是只能被1和它本身整除的数，所以2是最小的质数。在一篇论文中曾描述过质数分辨定理『n个不同的质数可以“分辨”的连续整数个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能有完全相同的余数序列』。
人们发现int类型最大能表示21亿个数，10个连续的质数能分辨的整数个数为 2*3*5*7*11*13*17*19*23*29=6464693230这个数超过了21亿，也就是说任何数经过10次以内计算肯定能找到。这就是为什么它查询快了。
看完是不是一脸蒙蔽，我还是用一个小栗子来说一下这棵树吧。
一个数除以2，余数有几种？0和1，所以哈希树的第2层有两个叉。查询就是根据余数判别走哪条路，一个数先除以2，根据余数找到分叉，用商除以3，根据余数找到分叉，再用商除以5。。。。不断的除下去，直到根据余数找到对应的数，或者跟本找不到为空。这就是哈希树。
1.2链表和顺序表的区别
顺序表中元素存储位置是相邻连续的，是可以快速访问到任何元素的一种数据结构。一个顺序表在使用前必须指定好存储空间大小，一旦分配内存就不可轻易更改。优点就是查询快速，缺点是插入非尾端数据或删除非尾端数据麻烦。顺序表由两部分组成，一部分是元素集合，一部分是有关表整体情况的信息（主要包括元素存储区的容量和元素的个数）。实现的方式为一体式和分离式，顾名思义，以顺序表两部分的情况区分。python中的list就是利用分离式顺序表实现的。
顺序表的构建需要预先知道数据大小来申请连续的存储空间，而进行扩充的时候，又不得不进行数据的搬迁，使用起来不是很灵活。为了充分利用计算机的内存空间，实现灵活的内存动态管理，我们就用到了链表。链表作为一种基础的数据结构，与顺序表不同，它是通过指针来描述元素关系的一种数据结构。它保存元素的时候，内存空间可以是不连续的，每个节点保存元素和下一个元素的指针即可。优点显而易见，但是缺点也很明显，就是查找元素必须重头开始查找。
1.3用代码实现一个死锁
假如一个线程在未释放锁的情况下发生了意外终止响应，其他线程获取不到锁而一直等待，这就是造成了死锁。下面我们利用简单的几行代码来模拟一个死锁的情况：
import threading
import time
# 创建互斥锁
lock = threading.Lock()
# 根据下标去取值， 保证同一时刻只能有一个线程去取值
def get_value(index):
# 上锁
lock.acquire()
print(threading.current_thread())
my_list = [3,6,8,1]
# 判断下标释放越界
if index >= len(my_list):
print("下标越界:", index)
return
value = my_list[index]
print(value)
time.sleep(0.2)
# 释放锁
lock.release()
if __name__ == '__main__':
# 模拟大量线程去执行取值操作
for i in range(30):
sub_thread = threading.Thread(target=get_value, args=(i,))
sub_thread.start()死锁产生后，程序会发生停止响应，空耗资源。为了避免此种情况，我们需要在合适的地方释放锁。
优质文章推荐: