daily pastebin goal
11%
SHARE
TWEET

Untitled

a guest Jan 22nd, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. use std::mem::swap;
  2.  
  3. fn main() {
  4.     let mut set = HashSet::new();
  5.  
  6.     for n in 0..=2000 {
  7.         assert!(!set.has(n));
  8.     }
  9.  
  10.     for n in 1..=1000 {
  11.         set.insert(n);
  12.     }
  13.  
  14.     for n in 5..=55 {
  15.         set.insert(n);
  16.     }
  17.  
  18.     for n in 1001..=2000 {
  19.         assert!(!set.has(n));
  20.     }
  21.  
  22.     for n in 1..=1000 {
  23.         assert!(set.has(n));
  24.     }
  25. }
  26.  
  27. type Value = i64;
  28. pub struct HashSet {
  29.     len: usize,
  30.     slots: Vec<HashSetSlot>,
  31. }
  32.  
  33. impl HashSet {
  34.     // the maximum number of slots per value before we shrink the vec.
  35.     const MAX_LOAD_RATIO: usize = 4;
  36.     // the number of slots per value we allocate when resizing the vec.
  37.     const TARGET_LOAD_RATIO: usize = 3;
  38.     // the minimum number of slots per value befoe we grow the vec.
  39.     const MIN_LOAD_RATIO: usize = 2;
  40.  
  41.     // Creates a new, empty, hash set.
  42.     pub fn new() -> Self {
  43.         HashSet {
  44.             len: 0,
  45.             slots: Vec::new(),
  46.         }
  47.     }
  48.  
  49.     // The number of items in the set.
  50.     pub fn len(&mut self) -> usize {
  51.         self.len
  52.     }
  53.  
  54.     // Inserts a value into this hash set.
  55.     //
  56.     // If an equal value already exists, it will be replaced by
  57.     // the new value. This is a non-op, unless the type can have,
  58.     // different values which are equal to each other, which is
  59.     // a hack but might let us build HashMap on top of this.
  60.     pub fn insert(&mut self, value: Value) {
  61.         self.resize_if_neccessary(self.len + 1);
  62.         self.do_insert(value);
  63.     }
  64.  
  65.     // Actually inserts the value into the backing slot vec.
  66.     fn do_insert(&mut self, value: Value) {
  67.         let hash = self.hash(value);
  68.         let mut index = hash % self.slots.len();
  69.  
  70.         loop {
  71.             match &self.slots[index] {
  72.                 HashSetSlot::Empty => {
  73.                     self.slots[index] = HashSetSlot::Value { value };
  74.                 },
  75.                 HashSetSlot::Value {
  76.                     value: colliding_value,
  77.                 } => {
  78.                     // copy value and drop the ref to slots
  79.                     let colliding_value = *colliding_value;
  80.                     // probe for next free index
  81.                     let mut next = index;
  82.                     while self.slots[next] != HashSetSlot::Empty {
  83.                         next = (next + 1) % self.slots.len();
  84.                     }
  85.                     // put our value there
  86.                     self.slots[next] = HashSetSlot::Value { value };
  87.                     // and put a pointer to it here
  88.                     self.slots[index] = HashSetSlot::CollidingValue {
  89.                         value: colliding_value,
  90.                         next,
  91.                     };
  92.                 },
  93.                 HashSetSlot::CollidingValue {
  94.                     value: _,
  95.                     next,
  96.                 } => {
  97.                     // follow the pointer
  98.                     index = *next;
  99.                     continue;
  100.                 },
  101.                 HashSetSlot::Tombstone { next } => {
  102.                     self.slots[index] = HashSetSlot::CollidingValue { value, next: *next };
  103.                 },
  104.             }
  105.             break;
  106.         }
  107.     }
  108.  
  109.     // Checks whether a value is present in the HashSet.
  110.     pub fn has(&self, value: Value) -> bool {
  111.         false
  112.     }
  113.  
  114.     // Resizes the underlying slot vec if neccessary.
  115.     fn resize_if_neccessary(&mut self, target_len: usize) {
  116.         let max_slots = target_len * Self::MAX_LOAD_RATIO;
  117.         let min_slots = target_len * Self::MIN_LOAD_RATIO;
  118.         let neccessary = self.slots.len() < min_slots || self.slots.len() > max_slots;
  119.         if neccessary {
  120.             let target_capacity = target_len * Self::TARGET_LOAD_RATIO;
  121.             let mut new_slots = vec![HashSetSlot::Empty; target_capacity];
  122.             swap(&mut new_slots, &mut self.slots);
  123.             let old_slots = new_slots;
  124.             for slot in old_slots {
  125.                 match slot {
  126.                     HashSetSlot::Value { value } => self.do_insert(value),
  127.                     HashSetSlot::CollidingValue { value, next } => self.do_insert(value),
  128.                     HashSetSlot::Empty => {}
  129.                     HashSetSlot::Tombstone { next } => {}
  130.                 }
  131.             }
  132.         }
  133.     }
  134.  
  135.     // Hashes a value into an integer digest.
  136.     pub fn hash(&self, value: Value) -> usize {
  137.         // TODO: consider actually implementing a hash if you must
  138.         value as usize
  139.     }
  140. }
  141.  
  142. #[derive(Debug, Clone, Copy, PartialEq)]
  143. enum HashSetSlot {
  144.     // there is no value here
  145.     Empty,
  146.     // there is a value here, with no colliding values
  147.     Value { value: Value },
  148.     // there is a value here, but there is another value whose
  149.     // hash collided with this one, which you may find at the
  150.     // index specified by next.
  151.     CollidingValue { value: Value, next: usize },
  152.     // there is no value here, but there used to be, and a value
  153.     // that was colliding with it may be found at the index
  154.     // specified by next.
  155.     Tombstone { next: usize },
  156. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top