Tag Archives: datastructures

Hash table

A hash table allows you to implement an associative array (dictionary) data structure, with an average performance of O(1) for insert, delete, and search operations.

Below is an example of the simplest implementation of a hash map on nodeJS:

How does it work? Let’s watch the hands:

  • There is an array inside the hash map
  • Inside the array element is a pointer to the first node of the linked list
  • Memory is allocated for an array of pointers (for example 65535 elements)
  • Implement a hash function, the input is a dictionary key, and the output can do anything, but in the end it returns the index of the array element

How does the recording work:

  • The input is a key – value pair
  • The hash function returns an index by key
  • Get a linked list node from an array by index
  • We check if it matches the key
  • If it matches, then replace the value
  • If it doesn’t match, then we move on to the next node until we either find a node with the required key.
  • If the node is not found, then we create it at the end of the linked list

How does keyword search work:

  • The input is a key – value pair
  • The hash function returns an index by key
  • Get a linked list node from an array by index
  • We check if it matches the key
  • If it matches, then return the value
  • If it doesn’t match, then we move on to the next node until we either find a node with the required key.

Why do we need a linked list inside an array? Because of possible collisions when calculating the hash function. In this case, several different key-value pairs will be located at the same index in the array, in which case the linked list is traversed to find the required key.

Sources

https://ru.wikipedia.org/wiki/Hash table
https://www.youtube.com/watch?v=wg8hZxMRwcw

Source code

https://gitlab.com/demensdeum/datastructures

Stack Machine and RPN

Let’s say we need to implement a simple bytecode interpreter. What approach should we choose to implement this task?

The Stack data structure provides the ability to implement the simplest bytecode machine. Features and implementations of stack machines are described in many articles on the Western and domestic Internet, I will only mention that the Java virtual machine is an example of a stack machine.

The principle of the machine is simple: a program containing data and operation codes (opcodes) is fed to the input, and the necessary operations are implemented using stack manipulations. Let’s look at an example of a bytecode program for my stack machine:

пMVkcatS olleHП

The output will be the string “Hello StackVM”. The stack machine reads the program from left to right, loading the data into the stack symbol by symbol, and when the opcode appears in the – symbol, it implements the command using the stack.

Example of stack machine implementation on nodejs:

Reverse Polish Notation (RPN)

Stack machines are also easy to use for implementing calculators, using Reverse Polish Notation (postfix notation).
Example of a normal infix notation:
2*2+3*4

Converts to RPN:
22*34*+

To calculate the postfix notation we use a stack machine:
2 – to top of stack (stack: 2)
2 – to top of stack (stack: 2,2)
* – get the top of the stack twice, multiply the result, push to the top of the stack (stack: 4)
3 – to top of stack (stack: 4, 3)
4 – on top of stack (stack: 4, 3, 4)
* – get the top of the stack twice, multiply the result, push to the top of the stack (stack: 4, 12)
+ – get the top of the stack twice, add the result, push to the top of the stack (stack: 16)

As you can see, the result of operations 16 remains on the stack, it can be printed by implementing stack printing opcodes, for example:
p22*34*+P

П – opcode to start printing the stack, п – opcode to finish printing the stack and sending the final line for rendering.
To convert arithmetic operations from infix to postfix, Edsger Dijkstra’s algorithm called “Sorting Yard” is used. An example of the implementation can be seen above, or in the repository of the stack machine project on nodejs below.

Sources

https://tech.badoo.com/ru/article/579/interpretatory-bajt-kodov-svoimi-rukami/
https://ru.wikipedia.org/wiki/Обратная_польская_запись

Source code

https://gitlab.com/demensdeum/stackvm/< /p>