Web caching is a temporary storage of web objects for later retrieval. This paper describes the improvement of web cache to develop a utility to share internet from single connection to a large network. This paper differs from the existing one as the former uses the data structures and databases for the storage and retrieval of the web pages. In this paper the usage of Randomized algorithms is implemented. Using this algorithm we replace the document in web cache in a effective manner. The randomized algorithms are used to clear the local folder, which has all the web pages saved in cache extension. Based on our analysis, we proposed a new algorithm which takes recently, frequency, perfect-history, and document size into account for web cache optimization. Considering all the above mentioned parameters the algorithm is proven to be efficient than its predecessors. This paper tries to resolve the problems in the existing system and provides improved algorithm, by which the performance of the web cache is improved.