// ********** CacheDemo.cpp **********
#include <iostream>
#include <time.h>
using namespace std;

class Integer {
  private:
    int i;
  public:
    Integer(int i) { this->i = i; }
    int intValue() { return i; }
};
class Node {
  private:
    int key;
    Integer* obj;
    Node* next;
  public:
     Node(int key, Integer* obj, Node* next) {
       this->key = key;
       this->obj = obj;
       this->next = next;
     }
     int getKey() { return key; }
     Integer* getObject() { return obj; }
     Node* getNext() { return next; }
};
class List {
  private:
    Node* head;
  public:
    List() { head = 0; }
    void enqueue(int key, Integer* obj) {
      head = new Node(key, obj, head); 
    }
    Integer* find(int key) {
      Node* current = head;
      while (current) {
        if (current->getKey() == key)
          return current->getObject();
        else
          current = current->getNext();
      }
     return 0;
    }
};
const int HASH_SIZE = 100;
class HashTable {
  private:
    List* array[HASH_SIZE];
  public:
    HashTable() {
      for (int i=0; i<HASH_SIZE; i++) 
        array[i] = new List();
    }
    int hashFunction(int key) {
      return key % HASH_SIZE;
    }
    void insert(int key, Integer* obj) {
      array[hashFunction(key)]->enqueue(key,obj); 
    }
    Integer* find(int key) {
      return array[hashFunction(key)]->find(key);
    }
};
int main() {
  clock_t t1 = clock();
  HashTable* hash = new HashTable();
  for (int i=0; i<10*HASH_SIZE*HASH_SIZE; i++) 
    hash->insert(i,new Integer(i));
  for (int i=0; i<10*HASH_SIZE*HASH_SIZE; i++) {
    Integer* j = hash->find(i);
  }
  clock_t t2 = clock();
  cout << (t2-t1)/1000 << " ";
  return 1;
}