Hashing

Study resources for Data Structures & Algorithms

Geeks for Geeks

Hashing

Dictionary and Set implement.

Applications:

• Dictionary
• Database indexing
• Cryptography
• Caches
• Data from Databases

Not used for :

• Finding closes value
• Sorted order

• Prefix searching -(Trie is better)

• Popular functions

  1. Append()
  2. Insert(loc, var)
  3. var in list
  4. count(var)
  5. index(var)–error if abscent index(var, start, end)
  6. remove(var)
  7. pop() –returns, index optional
  8. del list[index start : end]
  9. max, min, sum,list.reverse(), sort() –for strings only sum will not work
  10. map: ```python # input size of the list n = int(input(“Enter the size of list : “)) # store integrs in a list using map, # split and strip functions lst = list(map(int, input(“Enter the integer
      elements:”).strip().split()))[:n]

  # printing the list print(‘The list is:’, lst)

  ```

  1. Clear() Removes all items from the list
  2. copy() Returns a copy of the list

• Working:

  • Direct Address Table - problem Not handle large keys, floating point strings
  • Hash function- need to be fast, uniformly distribute large keys Examples

• Advantages:

  • Best for Search, Insert, Delete in BigO(1)
  • insertion ovverides if exist already, no duplicates

• DisAdvantages:

  • Strict search, yes or No.
  • No sorted order
  • Not handle large keys, floating point strings

• Other functions

  1. reduce() apply a particular function passed in its argument to all of the list elements stores the intermediate result and only returns the final summation value
  2. sum() Sums up the numbers in the list
  3. ord() Returns an integer representing the Unicode code point of the given Unicode character
  4. cmp() This function returns 1 if the first list is “greater” than the second list
  5. max() return maximum element of a given list
  6. min() return minimum element of a given list
  7. all() Returns true if all element is true or if the list is empty
  8. any() return true if any element of the list is true. if the list is empty, return false
  9. len() Returns length of the list or size of the list
  10. enumerate() Returns enumerate object of the list
  11. accumulate() apply a particular function passed in its argument to all of the list elements returns a list containing the intermediate results
  12. filter() tests if each element of a list is true or not
  13. map() returns a list of the results after applying the given function to each item of a given iterable
  14. lambda() This function can have any number of arguments but only one expression, which is evaluated and returned.

• Slicing

  1. Negative steps to reverse list
  2. gives different for list only. tuple gives same back…since immutable

• Comprehensions

Sets

do not contain duplicates. {}

• Sets

Dictionary

do not contain duplicates. {}

• Comprehensions

  • list(li) to set, dictionay d1 = {x:x**3 for x in l1} d1 = {x:f”ID{x}” for x in l1} d1 = {l2[i]:l3[i] for i in range(len(l2))} or **## d3 = dict(zip(l2,l3)) **
  • reverse dictionary d2 = {v:k for (k,v) in d1.items()}

## A New Post for resources to learn Data Structures & Algorithms

1. website
   • CodeWithHarry.
2. videos
   • CodeWithHarry playlist alternative if didn’t understand
   • nptelhrdplaylist
   • freeCodeCamp in jupyter notebook jovian
3. Practise and competitive matches
   • leetcode
   • neetcode
4. Pdfs
   • Coursera-Algorithms, Princeton University-coursera
   • Coursera-UC SanDiago
   • Ritika notes from LinkedIn

---

---