In the first part of this post, we'll design a simple fully-functional hash table, discuss its capabilities and limitations and outline a general approach to design a hash table that works well in practice. But understanding all the aspects of hash table design can be hard, and CPython's implementation is especially sophisticated, so we'll approach this topic gradually.
The goal of this post is to learn how CPython implements hash tables. And new, better designs are constantly being developed. There are different hash table designs that vary in complexity and performance. Yet, implementing a practical hash table is not a trivial task. The idea behind it is very simple and widely known. A hash table is a fundamental data structure. You probably know why this is the case: Python dictionaries are hash tables. What makes a dictionary appealing is that lookups and other dictionary operations are fast and that they remain fast even as we add more and more elements to the dictionary. CPython does a dictionary lookup every time you access an object attribute or a class variable, and accessing a global or built-in variable also involves a dictionary lookup if the result is not cached. Another reason is that the interpreter uses them internally to run Python code. Of course they are important because programmers use them a lot, but that's not the only reason. Python dictionaries are an extremely important part of Python. Tags: Python behind the scenes Python CPython
0 kommentar(er)
