A data existence judging device includes: L number of first storage areas each associated with one of L hash values; M number of second storage areas each associated with some of the L hash values; an information setting part, for each data in a data set, to calculate k hash values about the data, and, for each calculated hash value, when a count value in the first storage area associated with the calculated hash value is less than 2n−1, to count up the count value, whereas when the count value is 2n−1, to set 1 into the first storage area associated with the calculated hash value; and a judging part to calculate k hash values about an input data, and to judge that the input data is a new data when a count value in the first storage area associated with the input data is 0.