Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Random;
- public class Lab22 {
- static int probe = 0;
- public static void main(String args[]){
- int count = 0;
- while(count < 100){
- int m = 100000;
- Object[] T = new Object[m];
- int[] lup = new int[m];
- int[] ldown = new int[m];
- Random rand = new Random();
- for(int i = 0; i < 89999; i++){
- int value = rand.nextInt(100000);
- insert(T, value, lup, ldown);
- }
- probe = 0;
- insert(T, rand.nextInt(100000), lup, ldown);
- System.out.println(probe);
- count++;
- }
- }
- protected static int h(int x, Object[] T){
- return Math.floorMod(x, T.length);
- }
- protected static void insert(Object[] T, int x, int[] lup, int[] ldown) {
- int j = h(x, T);
- if (T[j] == null) {
- T[j] = x;
- } else {
- if (ldown[j] <= lup[j]) {
- hashInsertDown(T, x);
- ldown[j]++;
- } else {
- hashInsertUp(T,x);
- lup[j]++;
- }
- }
- }
- protected static void hashInsertDown(Object T[], int x) {
- for(int i = 0; i < T.length; i++) {
- int j = Math.floorMod(h(x, T) + i, T.length);
- if (T[j] == null){
- T[j] = x;
- return;
- }
- probe++;
- }
- System.out.println("Element "+x+" går ej att sätta in");
- }
- protected static void hashInsertUp(Object T[], int x) {
- for(int i = 0; i < T.length; i++){
- int j = Math.floorMod(h(x, T) - i, T.length);
- if (T[j] == null){
- T[j] = x;
- return;
- }
- probe++;
- }
- System.out.println("Element "+x+" går ej att sätta in");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement