Telephone - Good To Know Stuff

 

Today let's reminisce what was telephone and how it worked back then.

Telephone

• Telephone is common usage in Telecom, as it comprises telegram, television, fax, etc. 
• Teledensity is term which shows how many people are using telephone lines.
• A term commonly used to describe the number of telephone lines per some unit of the population (often per 100 people); the density of telephone. It also shows company's wealth.
• The different between telephone and computer is
• The old computer may not support to the current environment, whereas old model telephone can support to the environment but with the same features what it had.
• CTI => Computer Telephony Integration
• Voice Call recording system uses the following
• communicating with telephone
• on hook and off hook process

Analog Phones

• Analog telephones are dependent on voltages. It works on flow of voltage. It doesn't sends any packets.
• Types of Phones
• Rotary telephone
• Dial plan telephone
• Connection Settings
• Exchange ---- twisted pair wire ----> wall jack / rosette ---- twisted pair wire ----> local phone

• The local phone has two parts :
• headset
• connected with coiled wire
• twisted pair wire (copper wire) 
• red wire
• black wire
• jack
• base unit(box) or dialing box :
• Consists a place where the handset is kept, which is called "cradle".
• Consists two "hook switches", but now we have only one.
• Power
• The exchange gives power to phone.
• 50V dc power is sent to phone, when it is on hook state.
• The "multimeter" can measure the voltage passed.
• Dial Tone
• When the handset is picked up, a tone is played at the first is called dial tone.
• To check whether connection is established.
• To check the working state of the phone.
• If the dial tone is heard that means it is ready to use.
• Ring back
• The ring received after dialling the number.
• Handset place on the hook is called as on hook.
• Handset picked up then it is off hook.
• 70V AC is given when incoming call has come.
• While off hook is there then maximum voltage is given 20V to 28V.
• Flash => Getting the attention of the PBX. After that PBX will accept the numbers to perform some actions(hold). In the PBX certain numbers will be configured to respond that number.
• If the hook switches are pressed less than a second then we may get the attention of PBX.
• Oscilloscope is used to see the voltages.
• Rotary Dialler : The phone's dialler will be in a circle.

Architecture of Base Unit

                             

• hybrid : It will transform one type of signal to another. It is also meant as transducer. It is the very costly part of the base unit. The quality of the voice depends on this. The quality of the voice is evaluated here.
• capacitor : It will filter the AC from DC. It sends AC for ringing (incoming call). 
• In the on hook, the telephone will receive 50V.  When the incoming call comes the PBX will send 70V to our phone. When we make a call it will get a ring back tone from the PBX and the calling telephone will get 70V for ringing.
• The problem in this system is that, if the phone is disconnected from the wall jack then we too will get the ring back, it will just check the wall jack's connection not the wall jack to phone connection.
• In rotary phone, if we press the hook continuously, then there are chances of call to be made.
• When we pick up the handset, then the hook switch mechanism closes the switch. Then the voltage will be passed to the hybrid.
• To dial we will rotate the dialler, if we rotate zero then from the zero position it will open and close the dial switches(before hook switch) 10 times. All this will send pulse to the exchange, then the exchange will realise the pulse and calculate the number. All these pulses will be sent within a second. The one of the use of wall jack is that we can connect many telephones, else we can connect only one.

How Telephone Call Works

• After picking up the handset : Hear the dial tone passed by the PBX, this means the exchange is ready to serve.
• Dial the number, the dial tone will be stopped.
• Numbers are sent to the PBX in pulses, there it is counted and identifies the numbers. 

  Eg: The number dialled is 432.

  The pulse will be as following :

  _   _   _   _        _   _   _        _   _

               _| |_| |_| |_| |______| |_| |_| |______| |_| |_

                       4          |       3       |      2

                                  |               |

                                  V               V

• Inter digit Time : This is the time between the each digit pressed.
• Receive the ring back. And the other side receives 70V AC for ringing.
• The dial tone received back and voice will be of 400Hz purely which is modulated 20Hz.
• Then the connection is established, the voice will passed in pulses.
• All the combinations will be sent within a seconds, milliseconds or micro seconds.

Digital Phone

• Digital phone will send packets to communicate instead of sending voltages. 
• All the communication has been sent in 0s and 1s. 
• In digital, the header information like source address, destination address, etc., is used to send send and receive the packets.
• It is more intelligent and fast. 
• It gives lot of features of the analog phones.
• It gives constant power supply. 
• Unlimited signalling will be given.
• It has good speed to respond the request.
• Digital phones are fully dependent on PBX. So, if we use digital phone then the digital line has been made between phone and PBX.
• Noise tolerance.

VoIP

• It needs the network connection.
• It sends the data compressed in the packets format.
• It is more intelligent and faster compared to analog and digital.

Features of Telephones

• Ringing alert
• The LED will glow, if there are many telephones then to identify which phone is ringing.
• Ring volume controller 
• To control the volume, to minimize and maximize the call's volume.
• Automatic gain controller 
• To tune the voice.
• Flash button 
• To get the attention of PBX.
• Pulse and tone mode facility
• Can change the modes, but after the call completion it will reset to the original one.
• Hold button 
• To put a call in hold.
• Pause button 
• To pause a call, using this we can skip the IVR's options.
• Mute button
• To put a call in mute, this will avoid the user to hear us.
• Redialing 
• Wall mountable phones 
• Phones kept on the walls.
• Memory 
• Save the contact details.
• Hands free dialing 
• Echo cancellation 
• Subtracting the incoming and outgoing voice to avoid noise.
• Ringer Equivalent number 
• To obtain power consumption of the telephone.
• Caller id.

Telephone Exchange

                      Telephone Exchange

                  +------------+

      111(Phone) <------| *        * |-------> 101(Phone)

      112(Phone) <------| *        * |-------> 102(Phone)

      113(Phone) <------| *        * |-------> 103(Phone)

      114(Phone) <------| *        * |-------> 104(Phone)

      115(Phone) <------| *        * |-------> 105(Phone)

      116(Phone) <------| *        * |-------> 106(Phone)

                  +------------+

• A telephone exchange system acts as an intersection between two phone lines. 
• This is because a direct phone line between two establishments doesn’t actually exist.
• In the telephone exchange previously man intervention was needed. 
• This problem was solved by Mr. Strowger.  
• He designed the automated branch exchange.
• The communication can be done in only two ways analog(pulse) and digital(tone mode).
• Pulse Mode:
• Pulse mode refers to a way of signal transmission that involves sending electrical pulses down the telephone line.
• Pulse duration is short, measured in milliseconds or microseconds.
• Pulse is complicated.
• Tone Mode:
• Tone dialing refers to a way of transmitting signals in telecommunications systems that uses audio tones of different frequencies.
• Every digit when we press will have a frequency, which will be unique, to identify the number.
• The frequency is the combination of two frequencies. Since it will be difficult for the user to mishandle it, as this is very difficult to make the artificial voice.
• The tone is simple.
• There are phones now-a-days where we can change to Tone Mode or Pulse mode.

Telecommunication

Telecommunications such as radio, telephone, and television all use a method called multiplexing--shortened to "muxing"--to transmit and receive information.

Multiplexing

• Multiplexing was designed to send numerous analog signals or digital streams through one common transmission line.
• Multiplexing is the sharing of a communications channel through local combining of signals at a common point.
• One output, many input.

A------------+

B------------+ Multiplexing 

C------------+------------------- 

D------------+

De-Multiplexing

• Demultiplex (DEMUX) is the reverse of the multiplex (MUX) process – combining multiple unrelated analog or digital signal streams into one signal over a single shared medium, such as a single conductor of copper wire or fiber optic cable.
• Many output, one input.
• It is used for reducing the cost.

                         +------------- 

         De-Multiplexing +------------- 

        -----------------+------------- 

                         +------------- 

                         +------------- 

• Ex:
• A organization has 100 employees, get only one line from the exchange. From that make 100 connections.

TDM (Time Division multiplexing)

• This is also one of the methods in multiplexing which will work based on the time.
• The method of combining more than one independent data streams into a single data signal and transmitting that single data signal through a multiplexer to a demultiplexer is known as time-division multiplexing.

Ex :

----

   000|010 

A ---------+         +----------- A

   011|001 +   +------------+         +-------------+   +

B ---------+---+ Multiplexer+---------+ Demultiplex +---+----------- B

   111|100 +   +------------+         +-------------+   +

C ---------+            +----------- C

• Multiplexer read the data from the start(A) to end(B) within a second. If any channels are empty, it doesn't consider and send the data in a sequence. 
• Demultiplexer have control to identify the empty channels and separate the data using the given duration(one second). So first it reads the data 000 and 011 etc.
• First it takes all the data from the channels which has to be sent in the first one second. That will be passed into de-multiplexer. Then de-multiplexer separates the information based on the time. Here the time is one second but in real life it will be less than microseconds.
• Multiplexer does a multiplexing and De-Multiplexer does the de-multiplexing work. In between these two, one controlling terminal will be there for controlling the data. While passing it sends duration channels. Controlling terminal decides how many channels send that data.

Signalling

Analog Signals Features

• Accuracy
• Caller id is passed between rings.
• Analog Signal

      _           _           _           _           _

     / \         / \         / \         / \         / \

    /   \       /   \       /   \       /   \       /   \

----+   +-     -+   +-     -+   +-     -+   +-     -+   +------

          \   /       \   /       \   /       \   /

  \_/         \_/         \_/         \_/

Digital Signals Features

• Noise tolerance
• Avoid data loss
• Caller id is passed in packets.
• Digital Signal

                                           

    +---+   +---+   +---+   +---+   +---+  

    |   |   |   |   |   |   |   |   |   |  

----+   +---+   +---+   +---+   +---+   +------

PCM - Pulse code module

• This is a technique for converting analog signals into digital form.
• PCM samples the signal 8000 times a second, each sample is represented by 8 bits for a total of 64 Kbps.
• There are two standards for coding the sample level :
• Mu-Law 
• A-Law 

Sampling

• Sampling is a way to convert the analog to digital.
• Sampling rate means samples taken per second or hertz, the rate at which the samples of an analog signal are converted into digital form.
• To get original voice the sampling rate must be high.
• It requires double of bandwidth rate. Since the limiting factor is the bandwidth at which speech can be transmitted. 
• The 8000 samples per minute is taken for 64kbps.
• Example, the bandwidth telephone line we take as 64kbps at a sampling rate of 8kHz and 8-bits per sample.
• 8000 samples per second * 8-bits per sample = 64000bps = 64kpbs. 

Companding

• This is a technique used to compress data. It compresses the 16 bit data into 8 bit.
• This is formed from the words COMpressing and exPANDING. 
• Companding reduces the noise and crosstalk levels at the receiver by sending the compressed data and then expanding it at the receiving end to increase the signal quality when it is digitizing an analog signal.

CoDec

• The conversion of signals from analog to digital is performed by a coder. 
• On the receiving side, the process will be reversed using a decoder so that the signals can be used by an analog telephone.

PBX

• It is abbreviated as Public Branch eXchange.
• It is a switch station for telephone systems. It consists mainly of several branches of telephone systems and it switches connections to and from them (linking phone lines).
• To buy telephone for every employee of a organisation it will charge on the following basis :
• Wiring
• Rental
• Maintenance
• Deposit
• Call charge
• The calls made within the organisation costs heavily. Using PBX we multiple the phones.  Hence PBX is less expensive than connecting an external telephone line to every telephone in the organization.
• It's easier to call someone within a PBX, dial only 3 or 4 digits.
• It is like a hub, all the calls are routed to and from it.
• Two types of PBX:
• Soft PBX --> asterisk, freeswitch
• Hard PBX --> avaya, nortel, alcatel

PRI

• This is a type of ISDN.
• This is like a multiplexor, from a signal wire connected to the PBX 30 channels will be separated.
• This is a wire.
• This is an international communications standard for sending voice, video and data.

                           ------------ 701

                                    |

                                    |

                           ------------ 702

                                    |

                                    |

                           ------------ 703

   |

PRI --------- PBX  -------- |

                           ------------ 704

                                    |

                                    |

                           ------------ 705

                                    |

                                    |

                           ------------ 706

Cadence

• It is the pause between the rings.
• ring -- pause -- ring
• In America it is 4 seconds pause and 2 seconds ring.
• This differs based upon the country and PBX.

MSN

• The abbreviation is multiple subscriber number.
• These numbers will be given by exchange provider.
• E.G : from 700 to 799
• There can be many connections provided but only 30 can be simultaneously connected. 

Pilot Number

• It is a unique number given with a PRI connection.
• Example :
• From ABC, we are making a call and changing our profile details.
• We have changed our number to some other number which is not provided from MSN or it can be an invalid number.
• Then we will get a number as our caller number which is called pilot number.

ISDN 

• It stands for integrated service digital network. 
• It is communication standard which can be used between telephone exchange to telephone exchange and extension to extension.
• For communicating to the different exchange, one standard has to be followed that is ISDN.
• Types:
• BRI - Basic rate interface
• PRI - Primary rate interface 
• In BRI there are 2B channels and ID channel. In PRI there are 30B channels and 2D channels. 
• B channel -> Transfer the data(information)
• The speed of the B channel in BRI is 64 KBPS 
• D channel -> Control the data passed through B channel.
• The speed of the D channel in BRI is 16 KBPS 
• PRI Standards :
• E1 : European country introduces this standard. Indians are also using this standard.
• T1 : North America uses this type.
• J1 : Japan uses this type.

Type  Channels    Speed 

-----------------------------------

E1   (30B + 2D)  (64 Kbps + 64 Kbps )

T1   (23B + 1D)  (64 Kbps + 64 Kbps )

J1   Same as E1  (64 Kbps + 64 Kbps )

• For all the B channel only one D channel has been used. It is called as NFAS which will be used in T1 type standard.
• G7F1 is a standard which is used by B channel to send the data. The mulaw supply sampling rate is 8000 sp/s. For mulaw the sampling has been get as 16 bit and stored as 8 bit.
• G931 is a signalling method for controlling all the B channel. This standard is not only used for this. It is used globally in all the channels. Before sending the data it sends the packets in the channels for controlling the data.
• DID : It stands for direct inward dialling. It is a facility when the Multiple Service Numbers has been used. 
• Ex: In our organization MSN numbers are 43902701 - 43902799.
• ACD : It stands for Automatic Call Distribution which is used to route the calls to the appropriate systems.

Alcatel PBX

• The standard number is 4400.
• It has lot of wires such as power, extension, earth and PRI.
• It also has floppy, processor, hard disk.
• For knowing the status of extension LED's will be there.
• It transfers data in 0s and 1s.
• It uses the Unix OS.
• We can enable or disable any extension. 
• We can give the commands such as ping, ssh, traceroute, etc.
• If we need to add any device to the PBX, there no need to restart the PBX, since if we restart the data can be lost.
• It has the slots to add PRI.
• Main distribution framework : It is used to distribute the signals.

Facilities in the PBX

• Call parking
• It gives the numbers to park the calls. The parking is done based on the PBX.
• Call transferring
• Two types of transfer:
• Attended transfer (manual process needed to transfer the call to other person).
• Blind transfer (automated).
• Enquiry facility
• This is used to find out the line is busy or not.
• Queuing call
• If one number received more than one call at the same time, then the calls are made to be stand in the queue.
• Call waiting
• Conferencing
• Conference calls can be made.
• Wireless phone
• Noise tolerance 
• The noise and volume can be adjusted.
• Hunt Group
• Group of the extension numbers and call can be made to the group  number. 
• The call may be go simultaneously or one by one.
• Pick Group
• If you are in the same group then you can attend others call by typing # followed by the person's extension number.
• Chain dialling
• It is used to redirect the calls if one is not ready to attend.
• Heart Line
• Dedicate line for the extension. In this feature user don't need to type the numbers. 
• When the user picks up the handset, call goes automatically.
• Call follow me switch
• It is used to redirect the calls if one is not ready to attend with in a time.
• Call barring
• It is used to restrict the incoming call and outgoing call.
• Dynamic call barring
• It is used to restrict the call by some time.
• Call detailed record
• It is used to get call related informations. It is mainly used for billing purposes.
• Call budget
• It is used to restrict the minutes to speak.
• Call barging 
• It is used to hear the other's communication without their knowledge.
• Production from barging
• If we set this option no one can overhead of your conversation.
• DND ( Do Not Disturb )
• Toll Free Numbers ( Company will be charged )
• DSS (Digital station selector)  console
• It is used to control the calls and also used to restrict the extension numbers.

Asterisk

• It is open source soft PBX.
• Asterisk give the interface to configure all the things in easy.
• AsteriCon
• It has the details of asterisk meeting which happens every year.
• Switch matrix
• It is used to identify the capacity of PBX. How much matrices have based on that only the connection has been made.
• Least call routing
• The way of finding shortest path.

Credits and References

https://ars.els-cdn.com/content/image/3-s2.0-B9780080508030500101-f05-26-9780080508030.gif

https://media.hswstatic.com/eyJidWNrZXQiOiJjb250ZW50Lmhzd3N0YXRpYy5jb20iLCJrZXkiOiJnaWZcL3RlbGVwaG9uZTIuZ2lmIiwiZWRpdHMiOnsicmVzaXplIjp7IndpZHRoIjoyODV9fX0=

https://networkencyclopedia.com/plain-old-telephone-service-pots/

Coding Standards

Needs of Coding Standards

• Maintainable
• Proper understanding format / Readable
• Comments / Documentation
• Maintaining the changes done
• Reusable
• For doing a project we need a set of people in a set of teams, if everyone have perceptive to do code, then there will problems while integration of all the code (which all-together makes project). Hence the "Coding Standard" is needed.
• The time takes to understand the code must be less. Hence the source and comments must be easy and effective.
• If some code needs to modify or some new features needed to be added, for that the code clear(maintainable).

Coding Standards

Alignment

• Indentation is required.
• The tab size should be 4.
• The space is required after the function name and before parenthesis.
• After comma there should be a space.
• Within the square bracket there should not be any space.
• Use more parenthesis even if it is simple.
• The curly braces should be used in the following format for the conditions,  constructors and loops.

  if (condition) {

  ....

  } else {

  ....

  }

• The singe blank lines are required for the following :
• including files
• critical area
• block
• conditions and loops

• The double lines are required for the function.
• Declaring function
• Template : action_performed_verb
• The way to write a function :

function perform_addition () 

{

...

}

Naming

• Variable and function names can be in the combination of words.
• G_ is used for global variables declaration.
• The local variables should be shorter.
• T_ is used for temporary variables.
• The name should be meaningful, it should says it purpose.
• Proper naming must be there.
• Name separation must be done with an underscore("_").
• There can only 3 underscores at the max.
• For macros the capital letters are used.

• The parenthesis must be given, even if in some of languages its optional :

            if ( ( ( (condition) || (condition) ) && (condition) ) )

• Files
• Not only the variables and function names must be meaningful, but also the filenames should be proper.
• The file name can have the following :
• project_name
• sub_name
• purpose of file name

• Max
• 15 to 25 functions per file.
• 1000 lines of file
• One page scrollable code.

Comments

• Explanation
• Understanding
• Sample input and output
• Logical algorithm
• Function header
• File header
• Declaration usage
• Where form, where to

• Special Note
• REMIND
• TODO
• CAUTION
• NOTES  -> important values, notes

Credits and References

https://woz-u.com/blog/the-evolution-of-coding-what-programming-languages-are-prominent-today/ 

Define Manager - An Attempt

 

In the year 2008 I have recorded this as part of my notes. Today while checking the old notes got this and found it still so relatable and practical. Hence recording this here, to keep this notes handy :)

01. Should be a great organizer.

02. Should communicate more often.

03. Should be good listener with all.

04. Should look for solution instead of ones to blame.

05. Should like to work with people.

06. Should understand business story laying behind the project.

07. Should understand technical issues which appears during implementation.

08. Shouldn't hesitate whether to escalate or deliver negative feedback whenever needed.

09. Shouldn't get carried away over unfair opinions about your work and your projects.

10. Should always expect unexpected.

Please add your thoughts in the comments, let the list grows.

Dictionary and Set in Python - BTS

 

Introduction

In python dictionaries and sets are used to save unique, unordered(ordered from 3.7 python version explained below), mutable (also immutable - frozen sets) and quick retrieval elements. In any python program there are number of dicts used even when the program is not using it explicitly such as CPython uses dictionary lookup for any attribute or class or global variable and more. As this plays an important role it has been highly optimized by the python core developers, especially for search, add and delete operations. Hash tables are the key element behind the implementation of dicts and sets, making these data structures performance efficient. Hash tables are powerful and are also used in solving real life problems such indexing of database tables, caching, name lookups and so on.

Dictionary

A dictionary is composed of a series of key-value mapping elements. The keys and values can be of mixed types like string, integer 

• Create
• Below are few methods to create a dict
• a = dict(one=1, two=2, three=3)
• b = {'one': 1, 'two': 2, 'three': 3}
• c = dict(zip(['one', 'two', 'three'], [1, 2, 3]))
• d = dict([('one', 1), ('two', 2), ('three', 3)])
• e = dict({'one': 1, 'two': 2, 'three': 3})
• Possible key types, are all the immutable types such as str, bytes, numeric types
• Update

• The update() method inserts the specified items to the dictionary. The specified items can be a dictionary, or an iterable object with key value pairs.

• Eg:
• car = {

  "brand": "Ford",

  "model": "Mustang",

  "year": 1964

  }

  
  

  car.update({"color": "White"})

  
  

  print(car)

  
  
  

  Output:

  {'brand': 'Ford', 'model': 'Mustang', 'year': 1964, 'color': 'White'}
• Pop

• The pop() method removes the specified item from the dictionary and the value of the removed item is the return value of the pop() method.

• Eg:
• car = {

  "brand": "Ford",

  "model": "Mustang",

  "year": 1964

  }

  
  

  print("Pre Removed dict:", car)

  
  

  x = car.pop("model")

  
  

  print("Removed value:", x)

  print("Post Removed dict:", car)

  
  
  

  Output:

  Pre Removed dict: {'brand': 'Ford', 'model': 'Mustang', 'year': 1964}

  Removed value: Mustang

  Post Removed dict: {'brand': 'Ford', 'year': 1964}
• Get
• Return the default value  or None if the key does not existing, rather handling KeyError.
• __missing__
• The __missing__ method, is called by __getitem__() dictionary method internally if the keys doesn't exist. 
• The return value of __missing__() is the value returned when accessing the non existence key.
• Eg:
• sample_dict = {'name': 'python', 'age': 20}

  print(sample_dict['location'])

  
  

  Traceback (most recent call last):

  File "dict_set_sample.py", line 40, in <module>

  print(sample_dict['location'])

  KeyError: 'location'

  
  
  

  sample_dict = {'name': 'python', 'age': 20}

  print(sample_dict.get('location'))

  print(sample_dict.get('location', 'India'))

  
  

  Output:

  None

  India

• Items
• The items() method returns a view object.
• The view object contains the key-value pairs of the dictionary, as tuples in a list.
• The view object will reflect any changes done to the dictionary.
• Note: returned view object was part of version 3+, and here we have newly introduced __contains__ methods defined in python dict class to identify if the key exists in the dictionary or sets.
• Eg
• car = {

  "brand": "Ford",

  "model": "Mustang",

  "year": 1964

  }

  
  

  x = car.items()

  print(x)

  
  

  car["model"] = "Figo"

  print(x)

  
  
  

  Output:

  dict_items([('brand', 'Ford'), ('model', 'Mustang'), ('year', 1964)])

  dict_items([('brand', 'Ford'), ('model', 'Figo'), ('year', 1964)])

• Keys
• Method keys() returns a view object of all the available  first level keys in the dictionary.
• The view object contains the keys of the dictionary, as a list.
• The view object will reflect any changes done to the dictionary.
• Eg:
• car = {

  "brand": "Ford",

  "model": "Mustang",

  "year": 1964,

  "details": {

  "wheels": 4,

  "doors": 2,

  }

  }

  
  

  x = car.keys()

  print(x)

  
  
  

  Output:

  dict_keys(['brand', 'model', 'year', 'details'])
• Values
• values() is an inbuilt method in Python programming language that returns a view object. 
• The view object contains the values of the dictionary, as a list.
• The view object will reflect any changes done to the dictionary.
• Eg:
• car = {

  "brand": "Ford",

  "model": "Mustang",

  "year": 1964,

  "details": {

  "wheels": 4,

  "doors": 2,

  }

  }

  
  

  x = car.values()

  
  

  print(x)

  
  

  Output:

  dict_values(['Ford', 'Mustang', 1964, {'wheels': 4, 'doors': 2}])
• Filters
• Here we will just see some sample examples, but very good blog describes much more possibilities
• https://learnpython.com/blog/filter-dictionary-in-python/
• Filter dict with only partial matching values from dictionary:
• cars = {

  "ford_figo": 1990,

  "ford_focus": 1991,

  "ford_feista": 1992

  }

  
  

  print("Before drop of the column", cars)

  
  

  filter_str = "ford_feista"

  cars = dict(filter(lambda item: filter_str not in item[0], cars.items()))

  
  

  print("After drop of the column", cars)

  
  
  

  Output:

  Before drop of the column {'ford_figo': 1990, 'ford_focus': 1991, 'ford_feista': 1992}

  After drop of the column {'ford_figo': 1990, 'ford_focus': 1991}
• Filter and save empty values in dict
• cars = {

  "ford_figo": 1990,

  "ford_focus": 1991,

  "ford_feista": 1992,

  "ford_dummy": 0

  }

  
  

  print("Before drop of the column", cars)

  
  

  cars = dict(filter(lambda item: not item[1], cars.items()))

  
  

  print("After drop of the column", cars)

  
  
  

  Output:

  Before drop of the column {'ford_figo': 1990, 'ford_focus': 1991, 'ford_feista': 1992, 'ford_dummy': 0}

  After drop of the column {'ford_dummy': 0}
• Delete
• To delete the keys and delete the dictionary.
• Eg:
• dict1 = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

  print(dict1)

  # Delete a single element

  del dict1['a']

  print("post delete key dict1:", dict1)

  # Delete all elements in the dictionary

  dict1.clear()

  print("post clear dict1: ", dict1)

  dict2 = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

  # Delete the dictionary

  del dict2

  print("complete dict delete dict2: ", dict2)

  
  

  Output:

  {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

  post delete key dict1: {'b': 2, 'c': 3, 'd': 4, 'e': 5}

  post clear dict1: {}

  Traceback (most recent call last):

  File "dict_sample.py", line 134, in <module>

  print("complete dict delete dict2: ", dict2)

  NameError: name 'dict2' is not defined
• Fromkeys
• The fromkeys() method returns a dictionary with the specified keys and the specified value.
• It creates a new dictionary from the given sequence with the specific value else creates with None value assigned.
• Eg:
• types = ('flower', 'diamond', 'heart')

  cards = dict.fromkeys(types)

  print("Create a dict with None values:", cards)

  
  

  qty = [10]

  cards = dict.fromkeys(types, qty)

  print("Create a dict with default values:", cards)

  
  

  qty.append(3)

  print("View the created dict with updated list values:", cards)

  
  

  qty.pop(0)

  print("View the created dict with updated list values:", cards)

  
  
  

  Output:

  Create a dict with None values: {'flower': None, 'diamond': None, 'heart': None}

  Create a dict with default values: {'flower': [10], 'diamond': [10], 'heart': [10]}

  View the created dict with updated list values: {'flower': [10, 3], 'diamond': [10, 3], 'heart': [10, 3]}

  View the created dict with updated list values: {'flower': [3], 'diamond': [3], 'heart': [3]}
• Setdefault
• setdefault() returns the value of a key (if the key is in dictionary).
• Else, it inserts a key with the default value to the dictionary.
• Provides a significant speedup by avoiding redundant key lookups.
• Eg:
• d = {'a': 97, 'b': 98, 'c': 99, 'd': 100}

  ret_value = d.setdefault('e', 120)

  print("New key which does not exists in the dict, value: {}, dict: {}", ret_value, d)

  ret_value = d.setdefault('e', 140)

  print("New key which exists in the dict, value: {}, dict: {}", ret_value, d)

  
  
  

  Output:

  New key which does not exists in the dict, value: {}, dict: {} 120 {'a': 97, 'b': 98, 'c': 99, 'd': 100, 'e': 120}

  New key which exists in the dict, value: {}, dict: {} 120 {'a': 97, 'b': 98, 'c': 99, 'd': 100, 'e': 120}
• Defaultdict
• A defaultdict is configured to create items on demand whenever a missing key is searched.
• Internally it works by calling the callable provided to produce s default value.
• The callable that produces the default values is held in an instance attribute called default_factory.
• Eg:
• Create a defaultdict with a list constructor as default_factory
• index = collections.defaultdict(list)
• If the key is not found, an empty list is assigned to the new key.
• If no default_factory is provided, the usual KeyError is raised for the missing keys.
• Dict Comprehensions
• Transforming dictionary from one form to another using dict comprehensions.
• Dict comprehensions make the code easier to read, avoid loops and performance benefits.
• Explained the performance boost reason with dis output: 
• https://stackoverflow.com/questions/52542742/why-is-this-loop-faster-than-a-dictionary-comprehension-for-creating-a-dictionar
• Eg:
• dict1 = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

  # Double each value in the dictionary

  double_dict1 = {k:v*2 for (k,v) in dict1.items()}

  print(double_dict1)

  
  

  Output:

  {'a': 2, 'b': 4, 'c': 6, 'd': 8, 'e': 10}
• Very good reference sharing multiple examples:
• https://www.datacamp.com/tutorial/python-dictionary-comprehension
• Call by Reference
• Call by reference means that the argument passed to the function is a reference to a variable that already exists in memory rather than an independent copy of that variable. Hence any changes made to the variable will be impacted even after the function execution completes.
• Dictionary passed as argument is call by reference.
• Eg:
• dict1 = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

  
  

  def change(dict_val):

  print("inside change function before change:", dict_val)

  dict_val['new'] = 100

  print("inside change function after change:", dict_val)

  
  

  print("inside main function before change:", dict1)

  change(dict1)

  print("inside main function after change:", dict1)

  
  

  Output:

  inside main function before change: {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

  inside change function before change: {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

  inside change function after change: {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'new': 100}

  inside main function after change: {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'new': 100}
• Variations
• UserDict
• User can implement own dictionary by extending UserDict, which works like standard dict.
• It is preferred to use subclass from UserDict rather than from dict, as the builtin has some implementation shortcuts that end up forcing to override, which can be easily inherited from UserDict.
• Eg:
• # Python program to demonstrate Userdict

  from collections import UserDict

  # Creating a Dictionary where

  # deletion is not allowed

  class MyDict(UserDict):

  # Function to stop deletion

  # from dictionary

  def __del__(self):

  raise RuntimeError("Deletion not allowed")

  # Function to stop pop from

  # dictionary

  def pop(self, s = None):

  raise RuntimeError("Deletion not allowed")

  # Function to stop popitem

  # from Dictionary

  def popitem(self, s = None):

  raise RuntimeError("Deletion not allowed")

  # Driver's code

  d = MyDict({'a':1,

  'b': 2,

  'c': 3})

  print("Original Dictionary")

  print(d)

  d.pop(1)

  
  

  Output:

  Original Dictionary

  {'a': 1, 'b': 2, 'c': 3}

  Traceback (most recent call last):

  File "dict_sample.py", line 154, in <module>

  d.pop(1)

  File "dict_sample.py.py", line 139, in pop

  raise RuntimeError("Deletion not allowed")

  RuntimeError: Deletion not allowed

  Exception ignored in: <function MyDict.__del__ at 0x10955b8b0>

  Traceback (most recent call last):

  File "dict_sample.py.py", line 134, in __del__

  RuntimeError: Deletion not allowed
• OrderedDict
• Maintains the order of the insertion.
• The popitem method of an OrderedDict pops the first item by default, but if called by popitem(last=True) will return the last item added.
• Ordered dictionary is designed to remember the order of items, which is defined by the insertion order of keys. 
• When the value of a certain key is changed, the position of the key remains unchanged.
• Syntax: OrderedDict()
• Eg:
• from collections import OrderedDict

  
  

  numbers = OrderedDict()

  
  

  numbers["one"] = 1

  numbers["two"] = 2

  numbers["three"] = 3

  
  

  print(numbers) # OrderedDict([('one', 1), ('two', 2), ('three', 3)])
• Memory Allocation:
• As like dictionary the memory is allocated which grows linearly based on the number of keys added, but in ordered dictionary to maintain the order nearly 50% more memory is used to preserve the order of the items.
• Code:

from collections import OrderedDict

import sys




ordd = OrderedDict()

d = {}




for x in range(15):

ordd[x] = x

d[x] = x

print("ordered dict:", sys.getsizeof(ordd), "\t", "dict:", sys.getsizeof(d))







'''

Output:

-------

ordered dict: 392 dict: 232

ordered dict: 424 dict: 232

ordered dict: 456 dict: 232

ordered dict: 488 dict: 232

ordered dict: 520 dict: 232

ordered dict: 744 dict: 360

ordered dict: 776 dict: 360

ordered dict: 808 dict: 360

ordered dict: 840 dict: 360

ordered dict: 872 dict: 360

ordered dict: 1312 dict: 640

ordered dict: 1344 dict: 640

ordered dict: 1376 dict: 640

ordered dict: 1408 dict: 640

ordered dict: 1440 dict: 640

'''

• References:
• https://lerner.co.il/2019/05/12/python-dicts-and-memory-usage/
• Methods
• move_to_end: method is used to move an existing key of the dictionary either to the end or to the beginning. Eg:
• from collections import OrderedDict

  ord_dict = OrderedDict().fromkeys('GeeksForGeeks')

  print("Original Dictionary")

  print(ord_dict)

  # Move the key to end

  ord_dict.move_to_end('G')

  print("\nAfter moving key 'G' to end of dictionary :")

  print(ord_dict)

  # Move the key to beginning

  ord_dict.move_to_end('k', last = False)

  print("\nAfter moving Key in the Beginning :")

  print(ord_dict)

  
  

  Output:

  Original Dictionary

  OrderedDict([('G', None), ('e', None), ('k', None), ('s', None), ('F', None), ('o', None), ('r', None)])

  
  

  After moving key 'G' to end of dictionary :

  OrderedDict([('e', None), ('k', None), ('s', None), ('F', None), ('o', None), ('r', None), ('G', None)])

  
  

  After moving Key in the Beginning :

  OrderedDict([('k', None), ('e', None), ('s', None), ('F', None), ('o', None), ('r', None), ('G', None)])
• reversed: reverse the order of the dict keys stored. Eg:
• from collections import OrderedDict

  
  

  x = {'d':'four', 'e':'five', 'a':'one'}

  
  

  sample_reversed_dict = OrderedDict(reversed(list(x.items())))

  print("The reversed order dictionary : " + str(sample_reversed_dict))

  
  

  Output:

  The reversed order dictionary : OrderedDict([('a', 'one'), ('e', 'five'), ('d', 'four')])
• Counter
• Holds the count for each key, adding a new key will create a single count and updating the existing key will increase the count.
• Eg:
• from collections import Counter

  
  

  counter_dict_sample = Counter("helloworld")

  print(counter_dict_sample)

  
  

  Output:

  Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, 'w': 1, 'r': 1, 'd': 1})
• ChainMap
• Holds the list of dictionaries, where for key search will be performed based on the order of the dictionaries stored. 
• Eg: Interpreters use nested scopes, where each mapping represents a scope context.
• pylookup = ChainMap(locals(), globals(), vars(builtins)
• MappingProxyType
• Builds a read-only dictionary instance.
• Performance
• Time complexity for querying: O(1)
• Time complexity for storing: O(n)

• Calculating the count is going to slow down a Dictionary; it will take O(n) time complexity to calculate the counts for all keys (because each key will have to be hit at least once in order to append it's count to the running count stored in the value).

• Space complexity for storing: O(n) (During Hash Collision more than O(n))
• Let's look into a sample to see the performance list vs dict.
• Code:

import timeit

def find_number_in_list(lst, number):

if number in lst:

return True

else:

return False

short_list = list(range(100))

start = timeit.default_timer()

find_number_in_list(short_list, 1)

stop = timeit.default_timer()

print("--- short_list %s seconds ---" % (stop - start))

long_list = list(range(10000000))

start = timeit.default_timer()

find_number_in_list(long_list, 1)

stop = timeit.default_timer()

print("--- long_list %s seconds ---" % (stop - start))

def find_number_in_dict(dct, number):

if number in dct.keys():

return True

else:

return False

short_dict = {x:x*5 for x in range(1,100)}

start = timeit.default_timer()

find_number_in_dict(short_dict, 1)

stop = timeit.default_timer()

print("--- short_dict %s seconds ---" % (stop - start))

long_dict = {x:x*5 for x in range(1,10000000)}

find_number_in_dict(long_dict, 1)

stop = timeit.default_timer()

print("--- long_dict %s seconds ---" % (stop - start))

• Output

>> python list_vs_dict_time.py

--- short_list 1.0299999999990872e-06 seconds ---

--- long_list 4.7639999999904425e-06 seconds ---

--- short_dict 2.97399999998893e-06 seconds ---

--- long_dict 1.768262919 seconds --- 

• The fastest way to repeatedly lookup data with millions of entries in Python is using dictionaries. Because dictionaries are the built-in mapping type in Python thereby they are highly optimized. However, we have a typical space-time tradeoff in dictionaries and lists. Dict still use more memory than lists, since you need to use space for the keys and the lookup as well, while lists use space only for the values.
• In general O(1) to find the element in the dictionary. Though when this is hash collision we cannot say its always O(1).

Set

Set is a collection of unique objects. Set elements needs to be hashable. Frozen sets are part of sets which are immutable.

• Create
• Below are few methods to create a set
• a = set([1, 2, 3])
• b = {1, 2, 3} #Set literal
• Author from Fluent Python explains the set create using set literals are faster as calling set constructor requires to build a list and finally call set.
• Where as set literal directly calls specialized BUILD_SET bytecode
• Set doesn't support index operations as it is not built as list but using hash.
• s = {1, 2, 3}

  print(s[0])

  
  

  Traceback (most recent call last): File "dict_set_sample.py", line 44, in <module> print(s[0]) TypeError: 'set' object is not subscriptable
• Frozen set
• Immutable version of set.
• Eg:
• cars = set(['ford', 'renault', 'tata'])

  print(cars)

  
  

  cars.add("kia")

  print(cars)

  
  

  frozen_cars = frozenset(['ford', 'renault', 'tata'])

  print(frozen_cars)

  
  

  frozen_cars.add("kia")

  print(frozen_cars)

  
  

  
  

  Output:
  

  {'tata', 'renault', 'ford'}

  {'tata', 'renault', 'kia', 'ford'}

  frozenset({'tata', 'renault', 'ford'})

  Traceback (most recent call last):

  File "sample.py", line 121, in <module>

  frozen_cars.add("kia")

  AttributeError: 'frozenset' object has no attribute 'add'
• Set comprehensions
• Similar to any list/dict comprehensions, we have few different types of sample explained in the below blog - #veryhandy
• https://www.pythonforbeginners.com/basics/set-comprehension-in-python
• Eg:
• curSet = set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

  newSet = {element*3 for element in curSet}

  print("The Current set is:")

  print(curSet)

  print("The Newly Created set is:")

  print(newSet)

  
  

  
  

  Output:

  The Current set is:

  {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

  The Newly Created set is:

  {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}
• Set methods
• s.add(e) - Adds element e to s
• s.clear() - Remove all the elements of s
• s.copy() - Shallow copy of s
• s.discard(e) - Remove element e from s if it is present
• s.pop() - Remove element and return an element from s, raising KeyError if s is empty. However pop method removes the last element of the set and set itself is not ordered one needs to be cautious using this as any element could be removed.
• s.remove(e) - Remove element e from s, raising KeyError if e not in s
• s.isdisjoint(z) - Returns True if no elements in common from s and z
• Sort
• sorted(s) gives the sorts the set values, and returns the ordered output
• Eg:
• s = {3, 4, 2, 1}

  print(sorted(s))

  
  

  [1, 2, 3, 4]
• Set operators
• As the name suggests sets are ideally useful for performing set operations.
• Set operations as infix operators are useful to make the code easier to read and reason.
• Examples:
• s & z: s.__and__(z) - Intersection of s and z
• s | z: s.__or__(z) - Union of s and z
• s - z: s.__sub__(z) - Difference between s and z
• s ^ z: s.__xor__(z) - Symmetric difference
• e in s: s.__contains__(e) - Element e is present in s
• s < z: s.__le__(z) - Validates s is a subset of the z set
• s <= z: s.__lt__(z) - Validates s is proper subset of the z set
• s > z: s.__ge__(z) - Validates s is a super set of the z set
• s >= z: s.__gt__(z) - Validates s is proper super set of the z set
• s =& z: Intersection of s and z, s is updated
• Performance
• Sample performance validation to check the values in 
• Code:

def return_unique_values_using_list(values):

unique_value_list = []

for val in values:

if val not in unique_value_list:

unique_value_list.append(val)

return unique_value_list

def return_unique_values_using_set(values):

unique_value_set = set()

for val in values:

unique_value_set.add(val)

return unique_value_set

import time

id = [x for x in range(0, 100000)]

start_using_list = time.perf_counter()

return_unique_values_using_list(id)

end_using_list = time.perf_counter()

print("time elapse using list: {}".format(end_using_list - start_using_list))

start_using_set = time.perf_counter()

return_unique_values_using_set(id)

end_using_set = time.perf_counter()

print("time elapse using set: {}".format(end_using_set - start_using_set))

Output:

time elapse using list: 83.99319231199999 time elapse using set: 0.01616014200000393

• As we could see the performance between set vs list, set wins with a big impact.
• Time complexity for querying: O(1)
• Space complexity for storing: O(n)

Hash and Hash Tables

• Hash and Hash Tables are two different but inter-related concepts:
• Hash - Function to generate unique value for difference set of values
• Hash Tables - Is a data structure to implement dictionaries and sets. Basically data structure to save key and values.
• Hash
• A hash value for the given key to the hash function will always return same hash value. 
• The efficiency of the hash function is to turn the key into an index of the list, hence the effective hash function and list can determine the particular index of data in the list without search.
• Keys must be hashable objects
• For user defined dict class if __eq__ method is implemented it requires __hash__ also to be implemented, as it should make a == b to True and hash(a) == hash(b) to True as well.

• In Python 3, if you override __eq__, it automatically sets __hash__ to None, making the object unhashable, need to manually override __hash__ to make it hashable again.

• In python we have built-in hash function, used to generate unique value for different set of values
• Example of getting a same hash key running in same program, even if there is small variation the results completely differs.
• print(hash("Lorem"))

  print(hash("Lorem"))

  print(hash("Loren"))

  
  

  5675358576591581973

  5675358576591581973

  1733253194914647111
• Each rerun will produce random values and this is expected behaviour, this is used as a countermeasure against Denial-of-Service(DoS) or Hash Flooding making it secure difficult to attack. Hash flooding occurs when the attacker knows for the list of keys the hash function returns the same hash bucket, causing collision in turn this will take long time and freeze.
• If the language does not provide a randomized hash function or the application server does not recognize attacks using multi-collisions, an attacker can degenerate the hash table by sending lots of colliding keys. The algorithmic complexity of inserting n elements into the table then goes to O(n**2), making it possible to exhaust hours of CPU time using a single HTTP request. Reference: https://ocert.org/advisories/ocert-2011-003.html
• >> /usr/bin/python3 -c 'print(hash("Lorem"))'

  3856737851614672944

  >> /usr/bin/python3 -c 'print(hash("Lorem"))'

  3400600052546168698

  >> /usr/bin/python3 -c 'print(hash("Lorem"))'

  3757617178999059249
• At the time of writing this the below algorithm is used to generate hash by built-in hash. This was designed to prevent DoS attacks against hash tables - hash flooding is a concept (also known as HashDoS) is a denial of service attack that uses hash collisions to exploit the worst-case (linear probe) runtime of hash table lookups. 
• Along with SipHash, Random Salt is used.
• Salt, starting with Python 3.3, a random salt value is included when computing hash codes for str, bytes, and datetime objects, as documented in Issue 13703—Hash collision security issue. The salt value is constant within a Python process but varies between interpreter runs. With PEP-456, Python 3.4 adopted the SipHash cryptographic function to compute hash codes for str and bytes objects. The random salt and SipHash are security measures to prevent DoS attacks.
• Python 3.8.9. Reference: https://en.wikipedia.org/wiki/SipHash
• import sys

  print(sys.hash_info.algorithm)

  siphash24

• To disable hash randomization by setting a fixed seed value through the PYTHONHASHSEED environment variable.

• >> PYTHONHASHSEED=1 /usr/bin/python3 -c 'print(hash("Lorem"))'

  440669153173126140

  >> PYTHONHASHSEED=1 /usr/bin/python3 -c 'print(hash("Lorem"))'

  440669153173126140

  >> PYTHONHASHSEED=1 /usr/bin/python3 -c 'print(hash("Lorem"))'

  440669153173126140
• Instances of built-in mutable types—like lists, sets, and dicts—aren’t hashable. Only immutable objects are hashable (keys alone).
• >> /usr/bin/python3 -c 'hash([1, 2, 3])'  

Traceback (most recent call last):

File "<string>", line 1, in <module>

TypeError: unhashable type: 'list'

• Hash values small integers are equal to themselves, which is an implementation detail that CPython uses for simplicity and efficiency. The hash values don’t matter as long as you can calculate them in a deterministic way.
• print(hash(5))

  print(hash(500000))

  print(hash(50000000000))

  print(hash(500000000000000000000))

  print(hash(5000000000000000000000000000000))

  print(hash(50000000000000000000000000000000000000000))

  
  

  Output:

  5 500000 50000000000 1937910009842106584 20450418580029579 24958392007006097

• >>>[hash(i) for i in range(4)]

  [0, 1, 2, 3]

  
  

  Comment: cpython implementation dictobject.c

  
  

  This isn't necessarily bad!  

  To the contrary, in a table of size 2**i, 

  taking the low-order i bits as the initial table index is extremely fast, 

  and there are no collisions at all for dicts indexed by a contiguous range of ints. 

  So this gives better-than-random behavior in common cases, 

  and that's very desirable.
• To define a hash function for an object, define the __hash__ method.
• class HashToOne(object):

  def __hash__(self):

  return 1

  HTO = HashToOne()

  print(hash(HTO))

  
  

  Output:

  1
• To set an object as not hashable, set __hash__ to None.
• class NotHashable(object):

  __hash__ = None

  
  

  NH = NotHashable()

  print(hash(NH))

  
  
  Output:
  

  Traceback (most recent call last):

  File "dict_sample.py", line 94, in <module>

  print(hash(NH))

  TypeError: unhashable type: 'NotHashable'

• Defining own hash needs to be with caution, this could be easily misleading the actual implementation of datatypes and one may encounter subtle issues. Below article very clearly explains how it could break things and tips to resolve.

• https://www.asmeurer.com/blog/posts/what-happens-when-you-mess-with-hashing-in-python/
• Hash Tables
• Hash tables are the engines behind dicts and sets making it faster in order to achieve O(1). Here only the keys must be hashable. 
• Each position in hash table is called as bucket. 
• Caution: Please note the below example is one of its kind to handle hash collision but there are several types of it which we will discuss later. 



Credits: https://tenthousandmeters.com/blog/python-behind-the-scenes-10-how-python-dictionaries-work/

• Once the hash value is generated, its passed through a mathematical process to get the bucket number to be placed. Explained the process below in the Insertion.
• Simple version: bucket_index = hash(key) % number_of_buckets
• Yet another version: bucket_index = hash(key) % prime_number
• Hash table was initially built as sparse array which has empty cells, usually 1/3 or 1/2 would be empty cells.
• Sample dict: d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}
• Code Structure:
• struct dict {
  

  long num_items;
  

  dict_entry* items; /* pointer to array */
  

  }
  

  struct dict_entry {
  

  long hash;
  

  PyObject* key;
  

  PyObject* value;
  }
• Stored as :
• items = [['--', '--', '--'],

  [-8522787127447073495, 'barry', 'green'],

  ['--', '--', '--'],

  ['--', '--', '--'],

  ['--', '--', '--'],

  [-9092791511155847987, 'timmy', 'red'],

  ['--', '--', '--'],

  [-6480567542315338377, 'guido', 'blue']]
• Later after 3.6 the structure changed to make it compact and memory efficient.
• Code Structure:
• struct dict {
  long num_items;
  
  
  // new PyPy dictionary is split in two arrays
  variable_int *sparse_array;
  dict_entry* compact_array;
  }
  
  
  struct dict_entry {
  long hash;
  PyObject *key;
  PyObject *value;
  }
• Stored as:
• sparse_array = [None, 1, None, None, None, 0, None, 2]

  compact_array = [[-9092791511155847987, 'timmy', 'red'],

  [-8522787127447073495, 'barry', 'green'],

  [-6480567542315338377, 'guido', 'blue']]
• In the latest code structure change, the compact_array stores all the items in order of insertion the dictionary ordered is maintained, while sparse_array is a 1/2 to 2/3 full array of integers. 
• From: https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html. 
• The integers themselves are of the smallest size necessary for indexing the compact_array. So if compact_array has less than 256 items, then sparse_array will be made of bytes; if less than 2^16, it'll be two-byte integers; and so on. This design saves quite a bit of memory. 
• For example, on 64bit systems we can, but almost never, use indexing of more than 4 billion elements; and for small dicts, the extra sparse_array takes very little space.  For example a 100 element dict, would be on average for the original design on 64bit: 100 * 12/7 * WORD * 3 =~ 4100 bytes, while on new design it's 100 * 12/7 + 3 * WORD * 100 =~ 2600 bytes, quite a significant saving. 
• After reading the above example reminded me of Aniyan movie, if 1 person steals 5Rs it may not be impacting by if 5Lakhs people each steal 5Rs will be huge impact.
• With the reduced memory footprint, we can also expect better cache utilization.
• Only the data layout needs to change, rest all the hash table algorithms would stay the same, no change in hash functions or search order or collision statistics.
• Coming back here as well, if the hash table is filled it is copied to new location or resized for extra space (same like list once the list grows it will be resized).
• Hash Collision
• When the hash function gives the same value for different keys is known as hash collision. Below are few methods to address hash collision.
• Open Addressing: Spread the collided values in a predictable way that lets you retrieve them later. Sample several algorithms:
• Cuckoo hashing
• Double hashing
• Hopscotch hashing
• Linear probing
• Quadratic probing
• Robin Hood hashing
• Closed Addressing: Keep the collided values in a separate data structure to search through. Also known as separate chaining.
• Coalesced hashing: Combines the ideas behind both open and closed addressing into one algorithm.

• Insertion
• In a hash table for each item saved it contains two fields, hash mapping a reference to the key and a reference to the value of the item.  For sets it is only the value.
• For insert of key into the dict
• hash value is calculated using the built-in hash() function
• hash value is then performed an "and" operation for creating mask value so that it turns into an effective index to fit in an array (or bucket)
• if we have allocated 8 blocks of memory and our hash value is 28975, we consider the bucket at index 28975 & 0b111 = 7, however if the dictionary has grown to require 512 blocks of memory, then the mask becomes 0b111111111 and would consider the bucket at index 28975 & 0b11111111
• check if the returned index is already in use, if not insert the key and the value in to the block of memory
• if already in use and the key matches the given key update the value
• else if there is a collision meaning the hash function generated same hash value for two different keys, in such scenario to compute new index simple linear function is used called probing
• hash collision (perturb)
• Hash table with collision

Credits: https://www.oreilly.com/library/view/high-performance-python/9781449361747/ch04.html

• Search
• To find the position where it should be based on the hash value; then, compare the hash value and key of the element in this position to the hash table to see if it is equal to the element that needs to be found. 
• If they are equal, return directly; if they are not, then continue to search until a slot is found or an exception is thrown.
• Deletion
• For the delete operation, Python temporarily assigns a special value to the element at this position marking this as deleted. Order is preserved and then deletes from the compact array when the hash table is resized when many eateries needs to be cleared. Also reindexes the sparse array, as the positions changed.
• It is not difficult to understand that the occurrence of hash collisions tends to reduce the speed of dictionary and set operations. Therefore, in order to ensure its efficiency, the dictionary and the hash table in the collection are usually guaranteed to have at least 2/3 of the remaining space. 
• With the continuous insertion of elements, when the remaining space is less than 2/3, Python will regain a larger memory space and expand the hash table. 
• However, in this case, all element positions in the table will be re-arranged.
• Although the hash collision and the adjustment of the size of the hash table will slow down the speed, this happens very rarely. Therefore, on average, this can still ensure that the time complexity of insert, find, and delete is O(1).
• Dicts has significant memory overhead
• Even empty dictionary occupies more memory than list or tuples.
• Sample:
• import sys

  sample_dict = {}

  print(sample_dict, " size of empty dict", sys.getsizeof(sample_dict), type(sample_dict))

  sample_list = list()

  print(sample_list, " size of empty list", sys.getsizeof(sample_list), type(sample_list))

  
  
  

  Output:

  {} size of empty dict 64 <class 'dict'>

  [] size of empty list 56 <class 'list'>
• Though dicts require additional storage it brings in better performance. We can optimize and its the continuous process. One needs to remember optimization is the altar where maintainability is sacrificed.
• Modifying the dict while iterating is not a good idea.
• Set and frozenset types are also implemented with a hash table, except that each bucket holds only a reference to the element though slight variation in algorithms as dict we need to perform lookups whereas sets are used to save unique objects.

Conclusion

• A dictionary is composed of a series of key-value mapping elements.
• Compared with lists and tuples, the performance of dictionaries is better, especially for search, add, and delete operations. A dictionary can be completed within a constant time complexity.
• A set and a dictionary are basically the same, the only difference is that a set has no key-value pairing and is a series of disordered and unique element combinations.
• Source code: dictobject.c 

Finally a huge round of applause to python core developers, researchers and several other behind the scene engineers who want to make python better and efficient and secure! Huge Bow!!

References and Credits

• https://nolongerset.com/content/images/2020/12/key-5105878_1920.jpg
• Fluent Python - Luiano Ramalho
• https://github.com/python/cpython/blob/main/Objects/dictobject.c
• https://stackoverflow.com/questions/52023758/list-vs-dictionary-vs-set-for-finding-the-number-of-times-a-number-appears
• https://towardsdatascience.com/faster-lookups-in-python-1d7503e9cd38
• https://dzone.com/articles/python-memo-2-dictionary-vs-set-1
• https://www.oreilly.com/library/view/high-performance-python/9781449361747/ch04.html
• https://tenthousandmeters.com/blog/python-behind-the-scenes-10-how-python-dictionaries-work/
• https://realpython.com/python-hash-table/
• https://www.acunetix.com/vulnerabilities/web/php-hash-collision-denial-of-service-vulnerability/
• https://www.asmeurer.com/blog/posts/what-happens-when-you-mess-with-hashing-in-python/
• https://www.youtube.com/watch?v=npw4s1QTmPg
• https://www.geeksforgeeks.org/*/
• https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html
• https://mail.python.org/pipermail/python-dev/2012-December/123028.html
• https://www.fluentpython.com/extra/internals-of-sets-and-dicts/
• https://www.youtube.com/watch?v=66P5FMkWoVU&t=56s